Za prvé, Levenshteinova vzdálenost je definována jako minimální počet úprav nutných k transformaci řetězce A na řetězec B, kde úprava je vložení nebo odstranění jednoho znaku nebo nahrazení znaku jiným znakem. Takže je to do značné míry "rozdíl mezi dvěma strunami", pro určitou definici vzdálenosti. =)
Zní to, jako byste hledali funkci vzdálenosti F(A, B), která udává vzdálenost mezi řetězci A a B a práh N, kde řetězce se vzdáleností menší než N od sebe jsou kandidáty na překlepy. Kromě Levenshteinovy vzdálenosti můžete také zvážit Needleman–Wunsch . Je to v podstatě totéž, ale umožňuje vám poskytnout funkci, jak blízko je daná postava k jiné postavě. Tento algoritmus byste mohli použít se sadou vah, které odrážejí pozice kláves na klávesnici QWERTY, abyste odvedli docela dobrou práci při hledání překlepů. To by však mělo problémy s mezinárodními klávesnicemi.
Pokud máte k řetězců a chcete najít potenciální překlepy, počet srovnání, které musíte provést, je O(k^2). Kromě toho je každé srovnání O(délka(A)*délka(B)). Takže pokud máte milion řetězců, ocitnete se v potížích, pokud budete dělat věci naivně. Zde je několik návrhů, jak věci urychlit:
- Omlouvám se, pokud je to zřejmé, ale Levenshteinova vzdálenost je symetrická, takže se ujistěte, že nepočítáte F(A, B) a F(B, A).
- abs(len(A) - len(B)) je spodní mez vzdálenosti mezi řetězci A a B. Můžete tedy přeskočit kontrolu řetězců, jejichž délky jsou příliš odlišné.
Jeden problém, na který byste mohli narazit, je, že "1st St." má poměrně velkou vzdálenost od „První ulice“, i když je pravděpodobně chcete považovat za identické. Nejjednodušší způsob, jak to zvládnout, je pravděpodobně transformovat řetězce do kanonické formy před provedením porovnání. Takže můžete všechny řetězce napsat na malá písmena, použít slovník, který mapuje „1st“ na „first“ atd. Ten slovník může být docela velký, ale neznám lepší způsob, jak se s těmito problémy vypořádat.
Protože jste tuto otázku označili pomocí php, předpokládám, že k tomu chcete použít php. PHP má vestavěnou funkci levenshtein(), ale oba řetězce musí mít 255 znaků nebo méně. Pokud to nestačí, budete si muset vyrobit vlastní. Případně můžete zkoumat pomocí difflib Pythonu.