(Computer) science, bitch

Poslední dobou neřeším přímočaré úkoly, ale naopak věci, které jsou progresivně horší a horší. Začalo to tak, že jsem měl implementovat tkz. fuzzy search v seznamu názvů. To je vyhledávání, které vám vrátí výsledek, i když napíšete otázku s nějakou chybou. Dělá se to tak, že spočítáte editační vzdálenost pro všechna slova a vyberete ta s nejmenší.

Editační vzdálenost jenom znamená, kolik změn musíte udělat, abyste přeměnili řetězec A na řetězec B. Například X-Men a X-men má editační vzdálenost 1, protože musíte změnit velké M na malé m.

Samozřejmě, ten algoritmus na počítání editační vzdálenosti je přímo úměrný délce slov a těch slov máte řadově 10 na sedmou (10 000 000), takže pro každý dotaz počítat 10^7 editačních vzdálenosti je dosti nemocné. A co teď. Vědecký článek, podle kterého jsem to implementoval, uváděl dvě možnosti. Jedna byla aproximační (tj. nemá zaručeno, že slovo najde, přestože existuje) a rychlá, druhá kompletní ale 100 krát pomalejší.

První fungovala na bázi binárního vyhledávání. To znamená, že vezmete seřazený seznam a zeptáte se na prostřední prvek. Jestli se rovnají, máte výsledek. Jestli je větší, podíváte se na pravou polovinu. Pokud je menší, obdobně se podíváte na polovinu levou. Tam se opět podíváte na prostřední prvek a takhle pokračujete, dokud ho nenajdete, nebo už nebudete mít kde hledat. Funguje to úplně stejně, jako bisekce v matematice. Pokud vás zmátlo, jak se porovnávají textové řetězce, nejprve porovnáte první písmeno, pokud se rovnají, tak porovnáte druhé atd., je to klasické lexikografické řazení.

A teď jak do toho zakomponovat editační vzdálenosti? Předtím, než se zeptáme, jestli je prvek seznamu větší/menší, tak se podíváme na 5 jeho "sousedů" a pokud je jejich edit distance menší, než nějaký limit, tak je přidáme do seznamu. Idea je taková, že se s pomocí binárního vyhledávání dostaneme hodně blízko ke správným tvarům, a pak je stačí lapit sítí jako motýly. Samozřejmě tady se objevil problém, že pokud budete mít chybu někde hodně u začátku, tak binární vyhledávání "odskočí" moc brzo jinam a k hledanému slovu se nenajdete. Na to mého mentora napadla jedna hodně šílená věc. Celý seznam slov i náš hledaný termín převrátít (místo ahoj by bylo joha), a hledat to znova. Fakt to fungovalo, slova, co měla chyby hodně blízko začátku, je najednou měla na konci a fungovalo to mnohem lépe.

Yay.

Možná by stálo za to přemýšlet, jak náročné něco takového vlastně je. Pokud bychom hledali "normálně" přes všechna slova, vyžadovalo by to zminěných 10^7 porovnání.

S binárním vyhledáváním pokaždé půlíte seznam, takže pokud by v nejhorším případě došlo k log2(10^7) ~ 24 porovnáním. Ještě musíme vzít v potaz, že se díváme na 5 sousedních prvků, tak to vynásobíme 5. Následně to vynásobíme 2, protože se ptáme znova v obráceném seznamu.

Vychází to na zhruba 240. (pokud chete algoritmickou složitost, ta je logaritmická vzhledem k množství dat) 240 vs 10 000 000 je znatelný rozdíl.

Alternativou by bylo využití prefixových stromů (tkz. trie) s prohledáváním do hloubky a backtrackingem, ale o tom asi později a jenom pokud budu donucen to implementovat. Pls.

To je všechno krásný a růžový, ale díky tomu přišla úplně nová, naprosto nečekaná sada problémů, Náš fuzzy search byl až moc dobrý! Jeden z průserů byl, že předtím jsme se ptali na všemožné variace řetězců. Například u "when was Jesus born?" se pak ptáme na Jesus i Jesus born. Předtím, kdy to bylo hodně anální na správnost, vrátil Jesus výsledek a Jesus born nic. Teď, díky fuzzy hledání, vrátí i "Jesus born" mrdky jako "Jesus Borja".

Bohužel to bylo předtím nastavené tak, aby delší řetězce "pohlcovaly" kratší, takže Jesus se úplně ztratí. Haha, tak to je jasný, to přece nastavíme, aby teď naopak vyhrávaly řetězce s kratší editační vzdáleností (tj. co jsou víc správně). Na to jsem byl kontrován faktem, že pro X-Men Days of Future Past (bez dvojtečky) by vyhrál článek "X-Men", protože by měl nulovou editační vzdálenost, ale my bychom naopak chtěli ten film.

To jsou naprosto protichůdné problémy, které se skoro nedají řešit a trochu z nich šílím.






Komentáře

  1. Fascinující. Nezastavila jsem se, abych se zamyslela nad tou matikou, asi už to nejde automaticky. Meh. Ale je to fakt zajímavý.
    Cheers.
    - R.

    OdpovědětVymazat

Okomentovat

Populární příspěvky z tohoto blogu

Asian Squad

Dormking

Creating my own Point of Sale system, Part 1: Design