Frequency matching algorithm

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.