Първо, разстоянието на Левенщайн се дефинира като минималния брой редакции, необходими за трансформиране на низ А в низ Б, където редакцията е вмъкване или изтриване на единичен знак, или замяна на знак с друг знак. Така че това е много "разликата между две струни", за определена дефиниция на разстоянието. =)
Изглежда, че търсите функция за разстояние F(A, B), която дава разстояние между низове A и B и праг N, където низове с разстояние по-малко от N един от друг са кандидати за печатни грешки. В допълнение към разстоянието на Левенщайн можете също да помислите за Needleman–Wunsch . По принцип това е едно и също нещо, но ви позволява да предоставите функция за това колко близък е даден знак до друг знак. Можете да използвате този алгоритъм с набор от тежести, които отразяват позициите на клавишите на QWERTY клавиатура, за да свършите доста добра работа за намиране на печатни грешки. Това обаче би имало проблеми с международните клавиатури.
Ако имате k низове и искате да намерите потенциални правописни грешки, броят на сравненията, които трябва да направите, е O(k^2). Освен това всяко сравнение е O(len(A)*len(B)). Така че, ако имате милион струни, ще се окажете в беда, ако правите нещата наивно. Ето няколко предложения как да ускорите нещата:
- Извинете, ако това е очевидно, но разстоянието на Левещайн е симетрично, така че се уверете, че не изчислявате F(A, B) и F(B, A).
- abs(len(A) - len(B)) е долна граница на разстоянието между низовете A и B. Така че можете да пропуснете проверката на низове, чиито дължини са твърде различни.
Един проблем, с който може да се сблъскате, е, че "1st St." има доста голямо разстояние от "Първа улица", въпреки че вероятно искате да ги смятате за идентични. Най-лесният начин да се справите с това вероятно е да трансформирате низовете в канонична форма, преди да направите сравненията. Така че може да направите всички низове с малки букви, да използвате речник, който преобразува "1st" в "first" и т.н. Този речник може да стане доста голям, но не знам по-добър начин за справяне с този проблем.
Тъй като сте маркирали този въпрос с php, предполагам, че искате да използвате php за това. PHP има вградена функция levenshtein(), но и двата низа трябва да са 255 знака или по-малко. Ако това не е достатъчно дълго, ще трябва да го направите сами. Като алтернатива можете да разследвате с помощта на difflib на Python.
