Soundex • Alexander Piperski • Problemy naukowe na temat "Elementów" • Lingwistyka

Soundex

Soundex to algorytm kodowania nazw własnych. Powstał w latach 1918-1922. w USA, Robert Russell i Margaret King Odell, w celu ułatwienia poszukiwania podobnych brzmiących nazwisk. W połowie XX wieku Soundex był szeroko stosowany w USA w analizie wyników spisów ludności w latach 1890-1920. Poniżej znajduje się przykład spisu ludności z 1910 r. Tutaj widać, że kod Soundex dla nazwiska Wilson wygląda jak W425:

Zadanie

Lista nazwisk i odpowiadających im kodów Soundex jest podana w błędnym porządku. Brak niektórych znaków:

Allaway, Anderson, Ashcombe, Buckingham, Chapman, Colquhoun, Evans, Fairwright, Kingscott, Lewis, Littlejohns, Stanmore, Stubbs, Tocher, Tonks, Whytehead

S312, T␣6␣, ␣5␣3, C42␣, T520, L␣42, A536, C155, 623, S356, 252, ␣152, ␣330, A251, A400, L2␣0

Zadanie 1. Opisz krok po kroku, jak generowany jest kod Soundex.

Zadanie 2. Dopasuj nazwy i kody Soundex i wstaw brakujące znaki.

Zadanie 3. Twórz kody Soundex dla następujących nazw: Ferguson, Fitzgerald, Hamnett, Keefe, Maxwell, Razey, Shaw, Upfield.


Podpowiedź

Każdy kod składa się z litery i trzech cyfr. Litera powtarza pierwszą literę nazwiska, a cyfry kodują spółgłoski, które są w następnym nazwisku.


Rozwiązanie

Wszystkie kody Soundex składają się z litery łacińskiej i trzech cyfr. Nie jest trudno zgadnąć, dlaczego kod na nazwisko Wilson zaczyna się W: ponieważ jest to pierwsza litera tego imienia.

Gdy stało się jasne, że pierwsza litera jest zachowana, zadanie dzieli się na sześć małych zadań z zagmatwanymi odpowiednikami:

Allaway, Anderson, Ashcombe
A536, A251, A400

Chapman, Colquhoun
C42␣, C155

Lewis, Littlejohns
L42, L2␣0

Stanmore, Stubbs
S312, S356

Tocher, Tonks
T␣6␣, T520

Buckingham, Evans, Fairwright, Kingscott, Whytehead
␣5␣3, ␣623, ␣252, ␣152, ␣330

Przypomnijmy, że Soundex jest algorytmem zaprojektowanym, aby znaleźć podobnie brzmiące słowa. Prawdopodobnie liczby powinny zakodować jakiś charakterystyczny dźwięk. Można postawić hipotezę, że odpowiadają one literom spółgłoskowym znalezionym w nazwisku. To prawda, że ​​tylko sześć cyfr oznacza, że ​​ta sama cyfra koduje całe grupy spółgłosek.

Te grupy to:

bpv (f)cgjkqs (xz)dtlmnr
123456

Klasyfikacja liter w Soundex w mniejszym lub większym stopniu odpowiada klasyfikacji dźwięków zgodnie z ich wymową: grupa 1 zawiera spółgłoski wymawiane przy udziale warg; w grupie 2, spółgłoski wymawiane za pomocą języka i gwizdu; grupa 3 – przednie językowe zgryzy (d i t); w grupie 5 – nosowej. Postępując w ten sposób, możliwe jest rozpowszechnianie w grupach i listach, których nie widzieliśmy w warunku (w tabeli podano w nawiasach). List f wpadnie w grupę 1 do spółgłosek wargowych (już jest vpara f głuchota – dźwięczna), oraz x i z – w grupie 2 (x składa się z k i sktóre są w grupie 2, ale z – dzwonienie do pary s). Listy h i w Ta tabela nie została uwzględniona: są one ignorowane podczas generowania kodu Soundex. To samo dotyczy litery. yktóry w języku angielskim jest uważany za samogłoskę.

Możesz zauważyć, że kombinacje spółgłosek z jednej grupy odpowiadają tylko jednej cyfrze kodu. Na przykład z danych w stanie kodów nazwiska Kingscott może łączyć tylko ␣5␣3, w którym 5 jest odpowiedzialny n, 3 – dla ta numer w środku powinien być odpowiedzialny g, s i c (oczywiście, będzie to numer 2).

Zera w kodzie odpowiadają przypadkom, gdy spółgłoski nie wystarczają do wypełnienia trzech pozycji. Na przykład możesz to ustawić Allaway – to jest A400, gdzie dwa l odpowiada 4, i a, w, a i y nie uczestnicz w kodowaniu.

Odpowiedź na zadanie 1. Podsumowując wszystkie te obserwacje, możemy skonstruować algorytm kodowania. Ważne jest, aby zwracać uwagę na kolejność operacji, aby umożliwić otrzymywanie wszystkich kodów bez błędów.

1. Pozostaw pierwszą literę bez zmian.

2. Usuń h i w.

3. Wymień wszystkie spółgłoski na liczby (litery, najczęstsze odczyty są podobne, są połączone w grupy):

bfpvcgjkqsxzdtlmnr
123456

4. Dwie lub więcej identycznych liczb w rzędzie, aby zmniejszyć do jednego.

5. Usuń wszystkie samogłoski (a, e, i, o, u, y).

6. Pozostaw tylko pierwsze trzy cyfry lub dodaj zera po prawej, aby długość kodu wynosiła jedną literę i trzy cyfry.

Odpowiedz na zadanie 2 (Odzyskane znaki są podkreślone).

Allaway: A400, Anderson: A536, Ashcombe: A251, Buckingham: B252, Chapman: C155, Colquhoun: C425, Evans: E152, Fairwright: F623, Kingscott: K523, Lewis: L200, Littlejohns: L342, Stanmore: S356, Stubbs: S312, Tocher: T260, Tonks: T520, Whytehead: W330.

Odpowiedź na zadanie 3.

Ferguson: F622, Fitzgerald: F326, Hamnett: H530, Keefe: K100, Maxwell: M240, Razey: R200, Shaw: S000, Upfield: U143.


Posłowie

Zadanie, dla którego został użyty algorytm Soundex (i czasami nadal jest używane) jest zwykle nazywane rozmytym wyszukiwaniem ciągów (przybliżone dopasowywanie ciągów znaków, wyszukiwanie ciągów rozmytych).

Zdolność rozumienia, że ​​dwa wyrażenia językowe są równoważne, jest ważną częścią znajomości ludzkiego języka. Ta umiejętność może się przejawiać na różnych poziomach. Na przykład na poziomie semantyki (znaczenia słowa) i składni (powiązania między słowami w zdaniu i zdaniu), rosyjski mówca łatwo rozumie, że frazy Sto metrów długości przepłynął w czołgie w 45 sekund, Na sto metrów czołganie zajęło mu 45 sekund. i Przepłynął jaskinię za ¾ minutę (Apresyan 1995: I, 12) oznacza to samo. Podobnie na poziomie liter łatwo to rozumiemy Murawiow i Muravyev – to jest to samo nazwisko, ale Natalia i Natalia – o tej samej nazwie (chociaż w sytuacjach, w których chcę znaleźć błąd, możemy fałszywie powiedzieć coś w rodzaju: "Cóż, oczywiście, mówi Natalia Muravyovai masz paszport – Natalia Muravyova").Ale zautomatyzowanie tak podstawowej umiejętności, abyśmy mogli zrozumieć równoważność słów i wyrażeń, które nie do końca pasują, jest bardzo trudnym zadaniem.

Takie rozbieżności w praktyce występują regularnie. Soundex został pierwotnie wynaleziony właśnie do porównywania nazw własnych, ponieważ na początku XX wieku różnice w pisowni nazw własnych były znacznie wyższe niż obecnie, ale nawet teraz nie zostały całkowicie zredukowane do zera. W związku z tym książka (Lisbach, Meyer 2013: 15) podaje przykład dwóch opcji zapisywania informacji o tej samej osobie – na przykład z przesłuchania w call center i przepisywania z dokumentów z podziałem na pola:

Kate suzanne jankowiz
Belrive Str. 20, 65920 Frankfurt am Main (Niemcy)
CatherineSusanJenniferYankovits-brunner
20BellerivestrasseFrankfurt / M65920DE

Ważną zaletą Soundex, która pod wieloma względami zapewniała jej popularność, jest łatwość implementacji: w szczególności dla tego algorytmu nie jest potrzebny słownik. Soundex jest wymieniony w klasycznej sztuce Donalda Knutha The Art of Programming (Knuth 1998: 395-396). Jednak w pierwszym wydaniu (Knuth 1973: 391-392) autor nie uwzględnił jeszcze wszystkich subtelności i zasugerował jednocześnie wyrzucenie samogłosek, h i w; następnie na przykład Chapman nie daje Chapman → Capman → Ca15a5 → C155, i Chapman → Cpmn → C155 → C15 → C150.

Soundex jest wdrażany w kilkudziesięciu językach programowania. Na przykład wbudowana funkcja SOUNDEX znajduje się w systemie zarządzania bazami danych MySQL.A w Pythonie 3 możesz nagrać całą treść tego zadania w kilku linijkach (autor tego kodu to Ivan Derzhansky):

Wady Soundex leży na powierzchni. Czasami ten algorytm nie jest w stanie wykryć podobieństw między bardzo bliskimi nazwiskami: na przykład Levinson otrzyma kod L152, oraz Lewinson – kod L525. Ponadto Soundex nie działa dobrze w sytuacjach, gdy wymowa bardzo różni się od pisowni, co często dzieje się w języku angielskim. Na przykład szkockie nazwisko Colquhounpodana w warunku czyta coś w stylu Cahun, a jego kod Soundex C425 odzwierciedla nie do udowodnienia l (4) i q (2). Kolejną odmianą tego ostatniego nazwiska jest Colhoun (pamiętaj, że kapitan Cassius Kolhoun z "Headless Horseman" Mine Reed) – ma inny kod: okazuje się być C450. Jednak w takiej pisowni jest zwykle wymawiane l (Kolhun), więc różne kody w tym przypadku nie są takie złe.

Aby rozwiązać problem wyszukiwania rozmytego, często stosuje się bardziej zaawansowane algorytmy. Mogą to być zarówno fonetyczne algorytmy takie jak Soundex (na przykład Metaphone), jak i zupełnie inne podejścia – na przykład związane z odległością redakcyjną, zadanie, o którym już zostało opublikowane na naszej stronie.

Literatura:
1. Yu. D. Apresyan. Wybrane prace. T. I. // Semantyka leksykalna. M .: Języki kultury rosyjskiej, 1995.
2. Donald Knuth. Sztuka programowania komputerowego. Vol.3: Sortowanie i wyszukiwanie / czytanie (Msza św.), 1973.
3. Donald Knuth. Sztuka programowania komputerowego. Vol. 3: Sortowanie i wyszukiwanie. 2nd ed. // Reading (Mass.), 1998.
4. Bertrand Lisbach i Victoria Meyer. Dopasowanie tożsamości językowej // Wiesbaden: Springer, 2013.

Zadanie to wykorzystano na XIII Międzynarodowej Olimpiadzie Lingwistycznej w 2015 roku w Błagojewgradzie (Bułgaria).


Like this post? Please share to your friends:

;-) :| :x :twisted: :smile: :shock: :sad: :roll: :razz: :oops: :o :mrgreen: :lol: :idea: :grin: :evil: :cry: :cool: :arrow: :???: :?: :!: