PHP i podobieństwo dwóch wyrazów

pomylkaTrafiłem ostatnio na ciekawą sytuację. Blisko dziewięć lat temu napisałem system dla zarządzania awizacjami kierowców w magazynach dla największego w Polsce producenta wody. System do dziś supportuję i rozwijam. W międzyczasie przygotowałem integrację danych z SAPem do wymiany informacji za pomocą komunikatów EDI, które wysyłane i odbierane są za pomocą protokołu AS2. Jest to na szczęście już mój ostatni system napisany w PHP, który obsługuję (bo znacznie bardziej lubię Javę).

Ale to właśnie na tym polu zdarzyła mi się ciekawa sytuacja. Korporacja zleciła wprowadzenie zmiany w importach danych tak, aby system sam przydzielał przewoźników do zdefiniowanych tras, z odpowiednimi współczynnikami procentowymi w stosunku do wszystkich listów przewozowych na tych trasach.

Przez trasę rozumie się np. miejsce załadunku: Bielsko-Biała, miejsce dostawy: Warszawa. Dla niej system powinien przydzielać przewoźników dla nowych listów przewozowych według rozkładu procentowego: PPRZEWOŹNIK 1: 50%, PRZEWOŹNIK 2: 50%.

Cały problem polega na tym, że w danych importowych nie otrzymam bezpośrednio identyfikatora tej trasy, a system sam ma ją rozpoznać na podstawie… nazw miejscowości 🙂 To nie byłoby jeszcze jakimś większym problemem, gdyby nie fakt, że w importowanych danych z SAP jest mnóstwo pomyłek. Zobaczcie, co znalazłem dla miasta Bielsko-Biała:

  • Bielsko-Biała
  • Bielsko-Biala
  • Bielsko Biała
  • Bielsko Biala
  • Biesko Biała
  • Biesko-Biała
  • Bisko-Biała
  • BIELSKO BIAŁA
  • BIELSKO-BIAŁA
  • BIELSKO BIAŁ

Koszmar 🙂

Niestety nie było innego wyjścia i trzeba było zrobić rozpoznawanie trasy dla nowego listu przewozowego za pomocą nazwy miejscowości dostawy. Pierwszy raz spotkałem się z czymś takim, aby w produkcyjnym systemie dane miały być wiązane za pomocą danych tekstowych, które są tak nieprecyzyjne.

Patrząc na te powyższe przykłady od razu widzimy że odnoszą się do tego samego miasta: Bielsko-Biała. Ale jak zmusić nasz program aby widział to samo co my?

Odległość Levenshteina

Pierwszym pomysłem na rozwiązanie tego problemu było wykorzystanie odległości Levenshteina, czyli miary odmienności napisów, zaproponowana w 1965 roku przez Władimira Lewensztejna. Miara ta znajduje zastosowanie w przetwarzaniu informacji, danych w postaci ciągów symboli: w maszynowym rozpoznawaniu mowy, analizie DNA, rozpoznawaniu plagiatów, korekcie pisowni (np. wyszukiwanie w spisie telefonicznym błędnie podanego nazwiska), itp.

W skrócie odległość Levenshteina zwraca liczbę całkowitą równą ilości działań (wstawienie nowego, usunięcie i zmianę znaku w napisie) na inny znak które trzeba przeprowadzić aby dwa ciągi tekstowe były identyczne.

Np. odległość Levenshteina pomiędzy napisami identycznymi, np.

jest zerowa – skoro są identyczne, to potrzeba zero działań, by jeden z nich przeprowadzić na drugi.

Odległość Levenshteina pomiędzy napisami:

wynosi 1, ponieważ do przeprowadzenia pierwszego na drugi wystarcza jedno działanie: zamiana litery a na i.

Odległość pomiędzy napisami:

równa jest 3, ponieważ do przeprowadzenia pierwszego napisu na drugi potrzeba trzech działań: usunięcia liter y i k oraz wstawienia litery a.

Odległość pomiędzy napisami:

wynosi 4, ponieważ potrzeba co najmniej czterech działań, np.: usunięcia litery m, zamiany k na i oraz dodania d i a.

Funkcja PHP:

 

PHP similar_text()

W PHP jest jeszcze dostępna funkcja similar_text(), która została napisana na podstawie publikacji: „Programming Classics: Implementing the World’s Best Algorithms„, która zwraca ilość zgodnych znaków dwóch wyrażeń:

Dodatkowo w trzecim parametrze można przekazać referencję do zmiennej w które zostanie przypisany wynik procentowy podobieństwa.

 

Zdefiniujmy przypadki testowe

Ponieważ nie chcemy analizować wielkości liter ani żadnych białych znaków przyda się funkcja do konwersji:

Nie korzystamy z funkcji strtolower, bo nie zadziała dla polskich znaków.

Zbieramy wyniki dla każdej pozycji:

Wyniki:

MiastoMiasto lowercaseIlość znakówlevenshteinsimilar_textsimilar_text (procent)
Bielsko-Białabielsko-biała14014100
Bielsko-Bialabielsko-biala1321288.89
Bielsko Białabielsko biała1411392.86
Bielsko Bialabielsko biala1331181.48
Biesko Białabiesko biała1321288.89
Biesko-Białabiesko-biała1311396.3
Bisko-Białabisko-biała1221292.31
BIELSKO BIAŁAbielsko biała1411392.86
BIELSKO-BIAŁAbielsko-biała14014100
BIELSKO BIAŁbielsko biał1321288.89
Biała-Bielskobiała-bielsko1410750
Warszawawarszawa811327.27

Teraz trzeba podjąć decyzję – jaką wartość parametru przyjąć za graniczną w celu określenia czy dwa wyrażenia pasują do siebie. Jeśli przyjąć za założenie, że weryfikowane miasto jest zgodne z docelowym gdy zgodność procentowa jest na poziomie np. 80%, to wszystkie przypadki testowe zostaną prawidłowo rozpoznane.

Wydajność

Należy zwrócić uwagę na to, że standardowa funkcja levenshtein w PHP pozwala na porównywanie ciągów znaków do długości 255 znaków. Jeśli zostanie ona przekroczona zostanie zwrócony wynik -1.

Wywoływanie tych dwóch funkcji jest dość kosztowne, ich złożoność obliczeniowa wynosi:

  • levenshtein: O(m*n)
  • similar_text: O(max(n,m)^3)

Gdzie m i n są długościami wyrażeń. Jak widać funkcja levenshtein jest wydajniejniejsza pod względem funkcji similar_text. Ale mimo wszystko obie są dość kosztowne.

Implementacje w różnych językach programowania

Pod tym odnośnikiem znajdziecie implementacje algorytmu odległości Levenshteina w różnych językach programowania. Zarówno iteracyjne jak i rekurencyjne.

Podsumowanie

Problem przedstawiony na początku wpisu został rozwiązany, a przypadki pomyłek algorytmu (raczej dla krótkich nazw miejscowości) wysyłane są na monitoring systemu. Kluczową kwestią w takich rozwiązaniach jest odpowiednie dobranie parametru progu zgodności.

 

Autor: Matt Zandstra

ISBN: 978-83-246-9178-4

Format: , stron:

Data wydania:

Opis: Twój przewodnik po obiektowym PHP! Język PHP przebył długą drogę od swoich początków do obecnego poziomu rozwoju. Dziś jest pełnoprawnym, obiektowym językiem programowania, wciąż zdobywającym większe zaufanie i używanym w coraz większych projektach. Jeżeli znasz ten język od dawna, lecz nie jesteś przekonany, że nadaje się on do zaawansowanych zastosowa

Cena: 79.00zł

Autor: Peter MacIntyre, Brian Danchilla, Mladen Gogala

ISBN: 978-83-246-3922-9

Format: , stron:

Data wydania:

Opis: Zacznij tam, gdzie inni kończą! PHP jest obecnie najpopularniejszym językiem programowania aplikacji internetowych, a jego znajomość staje się koniecznością dla każdego programisty. "PHP Zaawansowane programowanie" zapozna Cię z nowymi możliwościami wersji 5.3.x, takimi jak przestrzenie nazw, funkcje anonimowe, Nowdoc, SPL oraz archiwa Phar. Doświadczeni programiści PHP

Cena: 59.00zł

To również może Cię zainteresować:

  • Hasła maskowane – błędy implementacyjne polskiego bankuHasła maskowane – błędy implementacyjne polskiego banku Ten tydzień zapisze się w historii polskiego internetu i bankowości za sprawą włamania do jednego z polskich banków. Jak podaje Zaufana Trzecia Strona przebieg wydarzeń wyglądał […]
  • Hasła maskowane ciąg dalszyHasła maskowane ciąg dalszy Pod ostatnim artykułem dotyczącym wpadki jednego z polskich banków pojawił się komentarz: Czy autor ma JAKIEKOLWIEK pojecia jak sa implementowane takie maski ? Z technicznego punktu […]
  • Arduino – sterowanie za pomocą aktywności mięśni dzięki Muscle Sensor 3Arduino – sterowanie za pomocą aktywności mięśni dzięki Muscle Sensor 3 Dotarła do mnie w tym tygodniu paczka z zamówionym SparkFun Muscle Sensor 3, za pomocą którego chciałem przetestować możliwość sterowania wyjściem Arduino poprzez sygnały odczytywane na […]
  • Odroid C1+, Odrobian i Kiosk modeOdroid C1+, Odrobian i Kiosk mode W jednym z naszych wdrożeń systemu ERP pojawiło się zapotrzebowanie na zaprojektowanie możliwości prezentacji aktualnego stanu na dockach załadunkowych w magazynie na przemysłowym […]
  • Bot do gry Arma 2 DayZ Epoch w C++Bot do gry Arma 2 DayZ Epoch w C++ DayZ Epoch do jeden z modów do gry Arma 2 (zaawansowanego symulatora pola walki) wprowadzający m.in. możliwość tworzenia budynków a w tym i zabezpieczania drzwi kłódką z trzy cyfrowym […]
  • Game streaming w nowych telewizorachGame streaming w nowych telewizorach Na samym początku wspomnę, że ten artykuł nie jest sponsorowany i mało związany z programowaniem - krótko zrecenzuję telewizor który ostatnio kupiłem. To czego szukałem w TV, to dobry […]

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *