Начало.
И так, с чего это все началось и откуда оно взялось?
В одном рабочем проекте потребовалось распознавать тексты(записи) на основе собственной базы. К примеру у нас есть база видео-карт для компьютера соответственно с названиями, и нам нужно сказать что то что нам прислали, это та или иная видео-карта из нашел базы.
Больше техники.
Перепробовав немало подходов и разных алгоритмов, остановился на алгоритме «Левенштейна» (Дистанция Левенштейна). [wiki]
Кому интересно, на вики есть формула и в примерах есть визуализатор алгоритмов.
«Расстояние Левенштейна (также редакционное расстояние или дистанция редактирования) между двумя строками в теории информации и компьютерной лингвистике — это минимальное количество операций вставки одного символа, удаления одного символа и замены одного символа на другой, необходимых для превращения одной строки в другую.» (c) wiki
Т.к. проект на перле, пришлось реализовать и это на перле. Вот что из этого получилось:
#!/usr/bin/perl
# так в книжке написано 
use strict;
# дебаггер
use Data::Dumper;
# что будем сравнивать
my $word1 = "ASUS NVIDIA PCI-E ENGTX550 TI DI/1GD5 ENGTX550 TI DI/1GD5 (90-C1CR70-L0UAY0YZ) [1137722]";
# наша база для сравнения
my @word2 = (
'ASUS GeForce GTX 550 Ti 1024 MB GDDR5 (ENGTX550 TI DC TOP/DI/1GD5)',
'ASUS GeForce GTX 550 Ti 1024 MB GDDR5 (ENGTX550 TI DC/DI/1GD5)',
'ASUS GeForce GTX 550 Ti 1024 MB GDDR5 (ENGTX550 TI/DI/1GD5)',
'ASUS GeForce GTX 560 Ti 1024 MB GDDR5 (ENGTX560 TI DCII TOP/2DI/1GD5)',
'ASUS GeForce GTX 560 Ti 1024 MB GDDR5 (ENGTX560 TI DCII/2DI/1GD5)',
'ASUS GeForce GTX 560 Ti 1024 MB GDDR5 (ENGTX560 TI DC/2DI/1GD5)',
'ASUS GeForce GTX 460 1024 MB GDDR5 (ENGTX460 DC TOP/2DI/1GD5/V2)',
'ASUS GeForce GTX 560 1024 MB GDDR5 (ENGTX560 DCII OC/2DI/1GD5)',
'ASUS GeForce GTX 560 1024 MB GDDR5 (ENGTX560 DCII TOP/2DI/1GD5)',
'ASUS GeForce GTX 460 1024 MB GDDR5 (ENGTX460 DirectCU TOP/2DI/1GD5)',
'ASUS GeForce GTX 560 1024 MB GDDR5 (ENGTX560 DC/2DI/1GD5)',
'ASUS GeForce GTX 460 1024 MB GDDR5 (ENGTX460 DIRECTCU/2DI/1GD5)',
'MSI GeForce GTX 550 Ti 1024 MB GDDR5 (N550GTX-Ti Cyclone II 1GD5/OC)',
'MSI GeForce GTX 550 Ti 1024 MB GDDR5 (N550GTX-Ti-M2D1GD5/OC)',
'MSI GeForce GTX 550 Ti 1024 MB GDDR5 (N550GTX-Ti Cyclone II 1GD5)',
'ASUS GeForce GTX 580 1536 MB GDDR5 (ENGTX580/2DI/1536MD5)',
'ASUS GeForce GTX 480 1536 MB GDDR5 (ENGTX480/G/2DI/1536MD5)',
'ASUS Eee PC 1015PEM-N550-N1BSAWM (90OA33BB3114987E23ZU)',
'ASUS Eee PC 1015PEM-N550-N1BSAP (90OA33BD3114987E23ZU)',
'ASUS Eee PC 1015PEM-N550-N1BSABL (90OA33B43114987E23ZU)'
);
my @dist = &distance($word1, @word2);
print Dumper(\@dist);
sub distance
{
my ($s,@t)=@_;
my $n=length($s);
my @result;
foreach my $t (@t) {
if ($s eq $t) {
push @result, 0;
next;
}
my @d;
my $cost=0;
my $m=length($t);
push @result,$m and next unless $n;
push @result,$n and next unless $m;
$d[0][0]=0;
foreach my $i (1 .. $n) {
if ($i != $n && substr($s,$i) eq substr($t,$i)) {
push @result,$i;next;
}
$d[$i][0]=$i;
}
foreach my $j (1 .. $m) {
if ($j != $m && substr($s,$j) eq substr($t,$j)) {
push @result,$j;next;
}
$d[0][$j]=$j;
}
for my $i (1 .. $n) {
my $s_i=substr($s,$i-1,1);
for my $j (1 .. $m) {
$d[$i][$j]=&_min($d[$i-1][$j]+1,
$d[$i][$j-1]+1,
$d[$i-1][$j-1]+($s_i eq substr($t,$j-1,1) ? 0 : 1) )
}
}
push @result,$d[$n][$m];
}
return @result;
}
sub _min
{
return $_[0] < $_[1]
? $_[0] < $_[2] ? $_[0] : $_[2]
: $_[1] < $_[2] ? $_[1] : $_[2];
}
На выходе получим что то такого вида:
$VAR1 = [
62,
60,
58,
64,
63,
62,
67,
65,
66,
67,
62,
65,
69,
68,
69,
64,
66,
67,
67,
67
];
Как мы видим из примера, 3-я в списке видеокарта, та которая нам нужна, и дистанция Левенштейна у нее будет минимальная (58) по отношению к другим видео-картам.
Наши выводы или что мы получили?
Алгоритм работает при небольших базах хорошо, как только начинаешь увеличивать количество слов(фраз) для сравнения, начинает определять не точно. При базе в 20 фраз, определяет с точностью до 90 процентов. Есть еще одна проблема, когда дистанция у двух или более фраз будет равна, пока еще не придумал решение для это ситуации. Думаю в скором времени мы увидим новые алгоритмы.
