Блог

Я пытаюсь проверить, есть ли какая-то строка в списке в заданном тексте. Но в данном тексте могут быть некоторые опечатки. Например, давайте возьмем это.

текст: Коричневый волк и кошка находятся в лесу. и мой список таков: [бурая лиса, лес, кошка]

Что я делаю на самом деле, чтобы сделать это, так это то, что я разделяю свой текст на несколько групп, групп из одного слова и двух слов, таких как: [The, brownw, focx, и, кошка, находятся, в, в, лесу, коричневая, коричневая, фокс, фокс и, и, кошка, кошка, находятся, в, в, в лесу]

Затем я повторяю каждую группу слов и проверяю с помощью алгоритма Левенштейна, насколько две строки совпадают друг с другом. В случае, если это более 90%, я считаю, что они одинаковы.

Однако этот подход требует очень много времени, и мне интересно, смогу ли я найти альтернативу этому.

Вместо того, чтобы использовать полное расстояние Левенштейна (которое вычисляется медленно), вы могли бы заранее провести пару проверок на вменяемость, чтобы попытаться исключить кандидатов, которые явно ошибаются:

1. длина слова: никогда не будет соответствовать коричневой лисе, так как она слишком короткая. Подсчитайте длину слова и исключите всех кандидатов, которые более чем на несколько букв короче или длиннее.
2. буквы: просто проверьте, какие буквы в слове. например, в нем нет ни одного письма от фокса, так что вы можете сразу исключить его. С короткими словами это может не иметь большого значения в производительности, но для более длинных слов это сойдет. Дополнительная оптимизация: сначала ищите редкие символы (x,q,w) или просто игнорируйте обычные (e, t,s), которые с большей вероятностью будут присутствовать в любом случае.

Эвристика, подобная этой, конечно, не даст вам правильного ответа, но она может помочь отфильтровать те, которые определенно не будут совпадать. Тогда вам нужно только выполнить более дорогостоящую полную проверку на гораздо меньшем количестве слов-кандидатов.