niedziela, kwietnia 15, 2007

Prosty spell checker, czyli jak umiejętnie połączyć teorie z praktyką

Trzy dni temu na blogu Google Operating System pojawił sie link do świetnego przykładu połączenia teorii z praktyką.Ten przykład to esej Petera Norviga o tym jak można w łatwy sposób stworzyć korektor ortograficzny, który ma skuteczność około 70%.Peter Norvig opisuje jak wychodząc z teoretycznych założeń dotyczących oceny prawdopodobieństwa czy słowo jest poprawne czy też nie, można zbudować prosty [liczący 21 linii] program w Pythonie 2.5, który potrafi dokonywać korekty błędnie napisanych słów.W skrócie cała idea opiera się na zbudowaniu modelu prawdopodobieństwa istnienia słowa na podstawie analizy statystycznej dużego zbioru słów - np. zbioru opowiadań ;-)Następnie bazując na założeniu, że w większości przypadków słowo jest błędnie zapisane ze względu na pominięcie jakiejś litery, wstawienie takowej, przestawienie lub zamienienie generowany jest zbiór nowych kandydatów na poprawną pisownię słowa. Każde testowane słowo służy więc do wygenerowania zbioru słów. Np. dla słowa "tka" wygenerowane zostaną przez usunięcie jednej litery słowa: "ta", "tk", "ka", poprzez przestawienie: "kta", "tak", poprzez zamianę litery słowa takie jak "aka", "bka", etc... Z tak zbudowanego zbioru wybierane jest najbardziej prawdopodobne słowo, które staje się propozycją poprawnej pisowni. Np. z naszych alternatyw słowa "kta", prawdopodobnie w polskich tekstach najczęściej spotkamy słowo "tak". Zachęcam do przeczytania eseju, naprawdę warto. Świetny przykład tego, że sucha teoria w połączeniu z praktyką czyni cuda :-)


Podobne postybeta
Jak automatycznie zmienić słowo "laka" w "łąka"? :-)
Testowanie upolskawiacza
Jak VHDL obalił komunizm
Zdjęciofilm 2 :-)
Sudoku solver - dalsza walka ;-)