Pokud porovnáváme cenu hotelového pokoje na různých webových stránkách, musíme se ujistit, že porovnáváme jablka s jablky
V informatice je fuzzy porovnávání řetězců technika hledání řetězců, které odpovídají vzoru přibližně (nikoli přesně). Jinými slovy, fuzzy porovnávání řetězců je typ vyhledávání, který najde shody, i když uživatelé špatně napíší slova nebo zadají jen část slov pro vyhledávání. Je také známý jako přibližná shoda řetězců.
Fuzzy vyhledávání řetězců lze použít v různých aplikacích, například:
- Kontrola pravopisu a oprava pravopisných chyb, překlepů. Například uživatel zadá do Googlu „Missisaga“, vrátí se mu seznam výsledků spolu se „Showing results for mississauga“. To znamená, že vyhledávací dotaz vrátí výsledky, i když uživatelův vstup obsahuje další nebo chybějící znaky nebo jiné typy pravopisných chyb.
- Software lze použít ke kontrole duplicitních záznamů. Například pokud je zákazník v databázi uveden vícekrát s různými nákupy kvůli odlišnému zápisu jeho jména (např. Abigail Martin vs. Abigail Martinez) nové adrese nebo chybně zadanému telefonnímu číslu.
Když už jsme u deduplikace, nemusí to být tak snadné, jak se zdá, zejména pokud máte statisíce záznamů. Ani Expedia to nedělá stoprocentně správně:
Tento příspěvek vysvětlí, co je to fuzzy string matching spolu s případy jeho použití a uvede příklady s využitím knihovny Fuzzywuzzy v jazyce Python.
Každý hotel má vlastní nomenklaturu pro pojmenování svých pokojů, stejný scénář platí i pro online cestovní agentury (OTA). Například jeden pokoj ve stejném hotelu nazývá Expedia „Studio, 1 King Bed with Sofa bed, Corner“, Booking.com může považovat za bezpečné zobrazit pokoj jednoduše jako „Corner King Studio“.
Není na tom nic špatného, ale mohlo by to vést ke zmatku, když chceme porovnat cenu pokoje mezi OTA, nebo když se chce jedna OTA ujistit, že jiná OTA dodržuje dohodu o paritě cen. Jinými slovy, abychom mohli porovnávat ceny, musíme se ujistit, že porovnáváme jablka s jablky.
Jedním z trvale nejvíce frustrujících problémů webových stránek a aplikací pro porovnávání cen je snaha zjistit, zda dvě položky (nebo hotelové pokoje) jsou automaticky za stejnou věc.
Fuzzywuzzy je knihovna pro Python, která používá Levenshteinovu vzdálenost k výpočtu rozdílů mezi posloupnostmi v jednoduše použitelném balíčku.
Pro demonstraci vytvořím vlastní soubor dat, to znamená, že pro stejné hotelové zařízení vezmu typ pokoje z Expedie, řekněme „Suite, 1 King Bed (Parlor)“, a pak ho porovnám s typem pokoje na Booking.com, který je „King Parlor Suite“. Při troše zkušeností většina lidí pozná, že jde o totéž. Podle této metodiky vytvořím malý soubor dat s více než 100 dvojicemi typů pokojů, který najdete na Githubu.
Pomocí tohoto souboru dat budeme testovat, jak Fuzzywuzzy uvažuje. Jinými slovy, použijeme Fuzzywuzzy k porovnání záznamů mezi dvěma zdroji dat.
import pandas as pddf = pd.read_csv('room_type.csv')
df.head(10)
Soubor dat jsem vytvořil já, takže, je velmi čistý.
Ve Fuzzywuzzy existuje několik způsobů porovnání dvou řetězců, vyzkoušejme je postupně.
-
ratio, porovnává se celá podobnost řetězců, a to v pořadí.
from fuzzywuzzy import fuzz
fuzz.ratio('Deluxe Room, 1 King Bed', 'Deluxe King Room')
Toto nám říká, že dvojice „Pokoj Deluxe, 1 manželská postel“ a „Pokoj Deluxe s manželskou postelí King“ jsou přibližně na 62 % stejné.
fuzz.ratio('Traditional Double Room, 2 Double Beds', 'Double Room with Two Double Beds')
Dvojice „Tradiční dvoulůžkový pokoj, 2 manželské postele“ a „Dvoulůžkový pokoj se dvěma manželskými postelemi“ jsou přibližně na 69 % stejné.
fuzz.ratio('Room, 2 Double Beds (19th to 25th Floors)', 'Two Double Beds - Location Room (19th to 25th Floors)')
Pár „Pokoj, 2 manželské postele (19. až 25. patro)“ a „Pokoj se dvěma manželskými postelemi – umístění (19. až 25. patro)“ jsou přibližně na 74 % stejné.
Jsem z nich zklamaný. Ukazuje se, že naivní přístup je příliš citlivý na drobné rozdíly v pořadí slov, chybějící slova nebo slova navíc a další podobné problémy.
-
partial_ratio, porovnává částečnou podobnost řetězců.
Stále používáme stejné dvojice dat.
fuzz.partial_ratio('Deluxe Room, 1 King Bed', 'Deluxe King Room')
fuzz.partial_ratio('Traditional Double Room, 2 Double Beds', 'Double Room with Two Double Beds')
fuzz.partial_ratio('Room, 2 Double Beds (19th to 25th Floors)', 'Two Double Beds - Location Room (19th to 25th Floors)')
Pro můj soubor dat nepřináší porovnávání částečných řetězců celkově lepší výsledky. Pokračujme.
-
token_sort_ratio, ignoruje pořadí slov.
fuzz.token_sort_ratio('Deluxe Room, 1 King Bed', 'Deluxe King Room')
fuzz.token_sort_ratio('Traditional Double Room, 2 Double Beds', 'Double Room with Two Double Beds')
fuzz.token_sort_ratio('Room, 2 Double Beds (19th to 25th Floors)', 'Two Double Beds - Location Room (19th to 25th Floors)')
Nejlepší zatím.
-
token_set_ratio, ignoruje duplicitní slova. Je to podobné s poměrem třídění tokenů, ale trochu pružnější.
fuzz.token_set_ratio('Deluxe Room, 1 King Bed', 'Deluxe King Room')
fuzz.token_set_ratio('Traditional Double Room, 2 Double Beds', 'Double Room with Two Double Beds')
fuzz.token_set_ratio('Room, 2 Double Beds (19th to 25th Floors)', 'Two Double Beds - Location Room (19th to 25th Floors)')
Vypadá to, že token_set_ratio je pro moje data nejvhodnější. Podle tohoto zjištění jsem se rozhodl použít token_set_ratio na celý svůj soubor dat.