Algorytmy

Frequency matching algorithm

  • 2006-06-29 20:34
  • 2 komentarze
  • 534 odsłony
  • Oceń ten tekst jako pierwszy
Algorytm frequency matching jest ciekawym algorytmem umożliwiającym porównywanie wyrazów, jest na tyle elastyczny, że pozwala określić poziom podobieństwa dwóch lub więcej wyrazów. Tutaj zajmiemy się dwoma wyrazami. Napiszmy funkcję implementującą ten algorytm, wykorzystajmy język Pascal. Najpierw zadeklarujmy tablicę typu bajt - tyle zajmuje jeden znak w pamięci, o 256 elementach - tyle mamy znaków ASCII. Niech będzie to zmienna globalna:

var letters: array [0..255] of integer;

Następnie zdefiniujmy nagłówek naszej funkcji, będzie ona przyjmować dwa argumenty - dwa łańcuchy do porównania i zwracać wynik typu bajt.

function freq_match (str1, str2: string): byte;

Przyda się nam także zmienna lokalna jako licznik pętli, oraz zmienna lokalna, która użyta w pętli przekaże wynik do funkcji, algorytm ten opiera się na pętli typu for...

var i, j: byte;

Pierwszym krokiem niech będzie zerowanie naszej tablicy:

for i:=0 to 255 do letters[i]:=0;

Jest to bardzo ważne, aby przed porównaniem kolejnym zawsze zerować naszą tablicę. Następnie zliczamy ilość wystąpienia danej litery w wyrazie pierwszym i wpisujemy odpowiednią wartość do odpowiadającej komórki. Jeszcze raz: do odpowiedniej komórki w tablicy (np. dla litery 'a' będzie to komórka nr. ord(a) - czyli o odpowiednim numerze danej litery w tablicy ASCII) dodajemy 1. Np. dla wyrazu 'hjerte' będzie to:

letters[ord('h')]=1;
letters[ord('j')]=1;
letters[ord('e')]=2; (bo litera wystąpiła dwa razy)
letters[ord('r')]=1;
letters[ord('t')]=1;

A oto pętla realizująca to zadanie:

for i:=1 to length (str1) do inc(letters[ord(str1[i])]);

Liczymy od 1 ponieważ w Pascalu, łańcuch w komórce nr.1 przechowuje aktualną długość swoją.

Z drugim wyrazem robimy to samo, lecz nie dodajemy jedynki lecz ją odejmujemy. Tak więc pod odpowiednią komórkę tym razem odejmiemy 1 (lub dodamy -1 jak kto woli). Wszystko oczywiście na tej samej tablicy. Oto pętla:

for i:=1 to length (str2) do dec(letters[ord(str2[i])]);

Teraz wystarczy zsumować wartość bezwzględną wszystkich liczb, które się znajdują w komórkach naszej tablicy:

for i:=0 to 255 do j:=j+abs(letters[i]);

I oczywiście zwrócić ją jako wynik funkcji:

freq_match:=j;

Im bardziej ta liczba będzie blika zeru, tym bardziej wyrazy są podobne. Jeżeli jest równa zero, znaczy to że wyrazy są takie same. Może się także zdażyć, że dwa oddzielne wyrazy mają taką samą liczbę takich samych liter. Wtedy nasza funkcja wygeneruje zły wynik (0) uznając, że ma do czynienia z tymi samymi wyrazami. Jest to w zasadzie jedyna niedogodność przedstawionego tu algorytmu frequency matching. A oto cały kod:

var letters: array [0..255] of integer;
function freq_match (str1, str2: string): byte;
var i, j: byte;
begin
  j:=0;
  for i:=0 to 255 do letters[i]:=0;
  for i:=1 to length (str1) do inc(letters[ord(str1[i])]);
  for i:=1 to length (str2) do dec(letters[ord(str2[i])]);
  for i:=0 to 255 do j:=j+abs(letters[i]);
  freq_match:=j;
end;
begin
  writeln (freq_match ('hjerte', 'hjerne'));
  writeln (freq_match ('hjerte', 'hjerte'));
end.

2 komentarze

wsw 2003-03-09 15:19

Algorytm nie jest wrażliwy na kolejność liter np. Basia wg. tego algorytmu to to samo co aisaB.
Korzystanie z tego algorytmu przy wyszukiwaniu np. ze słownika może dać bardzo dziwne wyniki

Pawlik67 2003-01-07 03:59

Hmmm.... :-)
Funkcja napisana przez Ciebie, Patkoss podaje właściwie wartość bezwzględną różnicy występujących liter w podanych dwóch wyrazach,  a nie porównuje czy wyrazy są identyczne czy nie :)
Tym nie mniej komuś może taki pomysł być do czegoś przydatny.
Pozdrawiam :-)