Preskočiť na obsah
Domovská stránka » Porovnávanie reťazcov

Porovnávanie reťazcov

  • Blog

Možno by nebolo zlé zohľadnovať v textovkách preklepy. Ako na to? Na meranie rozdielnosti dvoch reťazcov sa dajú použiť rôzne metódy, ale najviac sa mi osvedčili dve nasledujúce.

1) Levenshteinova vzdialenosť je algoritmus na nájdenie minimálneho počtu zmien znakov, ktoré treba urobiť, aby sme docielili zhodu zdrojových textov. Využívajú sa na to operácie ako vloženie, zmazanie znaku a substitúcia s rovnakou váhou. Odvodená Damerau Levenshteinova vzdialenosť podporuje naviac transpozíciu písmen, ktorú považuje za jednu úpravu.

2) Jaro Distance podporuje len transpozíciu písmen a zobrazuje vzdialenosti slov v intervale <0,1>. Jednotka predstavuje identické slová. Od toho odvodená Jaro-Winkler Distance zohľadňuje navyše aj dĺžku spoločného prefixu. Vďaka tomu dáva presnejšie výsledky pre reťazce so spoločným prefixom a je vhodnejšia na meranie vzdialeností slovenských slov.

Presnejší matematický popis sa dá ľahko nájsť na Wikipédii Damerau–Levenshtein distance a Jaro–Winkler distance. Rovnako aj zdrojové kódy nie je veľký problém nájsť. Nenašiel som však verziu pre Atari a Pedro ich pre mňa prepísal do Turbo-BASIC XL a keď už bol rozbehnutý urobil rovno aj verziu pre Action!.

 

Verzia pre Turbo-BASIC XL (veľkosť reťazcov 20 znakov)

Damerau Levenshtein Distance v Turbo-BASIC XL

Príklad ráta Levenshtein Distance a pokiaľ chcete Damerau Levenshtein Distance je nutné odkomentovať riadky 11750 až 11800. Po úprave príklad ráta Damerau Levenshtein Distance a pokiaľ chcete iba Levenshtein Distance je nutné zakomentovať riadky 11750 až 11800.

Jaro Winkler Distance v Turbo-BASIC XL

 

Verzia pre Action! (veľkosť reťazcov 14 znakov)

 

Damerau Levenshtein Distance v Action!

Opäť sa ráta Levenshtein Distance a pokiaľ chcete Damerau Levenshtein Distance je nutné odkomentovať zopár riadkov. Po úprave príklad ráta Damerau Levenshtein Distance a pokiaľ chcete iba Levenshtein Distance je nutné zakomentovať kód ;transposition for Damerau Levenshtein Distance. Len tak mimochodom, tá rýchlosť oproti Basicu je celkom slušný rozdiel 😉

Jaro Winkler Distance v Action!
S Jaro Winkler Distance nastupuje malá komplikácia. Action! podporuje len celé čísla 🙂 je preto nutné posunúť vhodne desatinnú čiarku a zaokrúhliť. Iste dalo by sa využiť matematické funkcie uložené v ROMke, ale to je zbytočne pracné.

Ukážka výpočtu Damerau Distance a Damerau Levenshtein Distance v oboch jazykoch:


Na príklade s QWERTY je pekne vydieť rozdiel v oboch spôsoboch výpočtu.

Ukážka výpočtu Jaro Winkler Distance v oboch jazykoch:

Ktorý z nich je Action! je myslím jasné 🙂

Príklady som prihodil aj na Rosetta Code
https://rosettacode.org/wiki/Levenshtein_distance
https://rosettacode.org/wiki/Jaro_distance

Download bol presunutý na github.com.

Pridal som tam aj príklad. Procedúru _EQUAL_ treba uvážlivo rozšíriť. Napríklad pre menšie slová ako 3 písmenká nepovoliť preklep a samozrejme treba zvážiť rýchlosť na 8bitoch.

Pridaj komentár

Vaša e-mailová adresa nebude zverejnená. Vyžadované polia sú označené *

Táto webová stránka používa Akismet na redukciu spamu. Získajte viac informácií o tom, ako sú vaše údaje z komentárov spracovávané.