Форум: "Основная";
Текущий архив: 2006.01.15;
Скачать: [xml.tar.bz2];
Вниз
Алгоритм сравнения строк Найти похожие ветки
← →
Dimedrol © (2005-12-12 15:09) [0]Коллеги, у меня есть задача: найти среди нескольких тысяч текстовых записей (<=200 знаков) похожие.
Я испробовал мой, где-то скачанный давным давно алгоритм сравнения строк, который выдает "похожесть" строк в процентах (очень полезная вещь!), но на 3000 тысячах записей,
он ооооооочень медленно работает.
Фактически, он работает почти 1 час.
Это медленно.
(могу кинуть исходник)
Пробовал SoundEX, причем написал DLL-ку на FreePas.
Все классно. Работает очень быстро, но очень не точно!
Т.к. если строках (<=200 знаков) 2-е слово разное,
то это уже - разное значение на выходе.
Это - не подходит.
И вот - хотел посоветоваться, - какие есть алгоритмы
для выполнения подобных задач ?
Я готов проверить все. :-)
По скорости.
Т.к. сейчас - в тупике.
PS
В моем алгоритме и в SoundEx я русский текст, да и вообще - весь текст, перевожу в заглавную латиницу, чтобы
не иметь проблем с языками.
← →
Tor © (2005-12-12 16:13) [1]Простые вопросы перекручивают в заумные.
Что значит "похожие"? Что бы в них одинаковые буквы были или что? :)
← →
TUser © (2005-12-12 16:14) [2]Ищи по ключевым словам "выравнивание" и "неточное сравнение строк".
← →
Jeer © (2005-12-12 16:31) [3]Вероятно, среди 200 символов надо отыскать смысловое содержание, похожее на еще какие-то 200 символов и так - все тома "Война - им мир":))
← →
Dimedrol © (2005-12-12 16:52) [4]2 Tor © & Jeer ©
"похожие", это значит, - даешь на вход 2 строки -
1. Мама мыла раму
2. Мама мыла Рому
И мой алгоритм "говорит", что - "мне переданы строки, похожие на 92%"!
Этот алгоритм у меня есть!
Только - медленный.
← →
Tor © (2005-12-12 17:04) [5]Че один символ это уже целых 8% ? :)
Ищи подстроку в строке, полубому тебе сравнивать все тома "Война и мир" сами с собой. А как ты там будеш процентное отношение получать это уже ... . Хоят зачем тебе процентное отношение? Мне кажеться это ни кому и ни где не нужно.
Если есть готовый алгоритм, проверь где он медлит и упрости ток участок, возможно это будет быстрее чем снова все придумавать. Всеравно тоже самое получится.
← →
Jeer © (2005-12-12 17:07) [6]А так - это тоже похожие ?
раму мама рыла
← →
Tor © (2005-12-12 17:18) [7]TUser Парвильно сказал. Тебе надо из строки выделять ключевую подстроку (причем это будут одиночные слова, а не фразы, если учитывать что слова могут быть в произвольном порядке, как Jeer привел пример) Береш набор слов и ищеш каждое слово в каждой строке. Ну короче перед тем как начинать решать такие задачи хорошо определяют надо ли такое или нет. Работа не сложная но достаточно "запутанная" и растянутая. Надо учитывать многие варианты и мелочи, иначе упрощай задачу.
← →
Leonid Troyanovsky © (2005-12-12 18:19) [8]
> Dimedrol © (12.12.05 16:52) [4]
> Этот алгоритм у меня есть!
Если это не А.Л. Грибов. "Простой алгоритм для решения задачи
идентификации символьных выражений" ,то, возможно, стоит
посмотреть и его:
http://rsdn.ru:80/File/13030/Probably2.doc
Во всяком случае, этот подход основан на некоторой
интуитивно-понятной модели.
Ну, а, вообще, чем более тщательно сформулированы условия
подобной задачи, тем больше шансов, IMHO, найти
правдоподобный ответ.
Т.е., например, можно попробывать искать:
алгоритмы нечеткого сравнения (поиска) строк.
--
Regards, LVT.
← →
Verg © (2005-12-12 19:39) [9]{
>> Расстояние (разность) между двумя строками. Функция Левенштейна
***************************************************** }
const cuthalf = 100; // константа, ограничивающая макс. длину
// обрабатываемых строк
var buf: array [0..((cuthalf * 2) - 1)] of integer; // рабочий буффер, заменяет
// матрицу, представленную
// в описании
function min3(a, b, c: integer): integer; // вспомогательная функция
begin
Result := a;
if b < Result then Result := b;
if c < Result then Result := c;
end;
// реализация функции в принципе соответствует описанию с одной оговоркой:
// матрица из описания заменена статическим буффером, длина которого
// равна удвоенной максимальной длине строк
// это сделано для 1) экономии памяти и во избежание её перераспределений
// 2) повышения быстродействия (у меня функция работает
// в обработчике onfilterRecord)
// таким образом, в реализации половинами буффера представлены только
// две последние строки матрицы, которые меняются местами каждую
// итерацию внешнего цикла (по i)... для определения того, какая из половин
// буффера является "нижней строкой", служит переменная flip
// т. е. при flip = false первая половина буффера является предпоследней
// строкой, а вторая - последней; при flip = true наоборот,
// первая половина - последняя строка, вторая половина - предпоследняя
function LeveDist(s, t: string): integer;
var i, j, m, n: integer;
cost: integer;
flip: boolean;
begin
s := copy(s, 1, cuthalf - 1);
t := copy(t, 1, cuthalf - 1);
m := length(s);
n := length(t);
if m = 0 then Result := n
else if n = 0 then Result := m
else begin
flip := false;
for i := 0 to n do buf[i] := i;
for i := 1 to m do begin
if flip then buf[0] := i
else buf[cuthalf] := i;
for j := 1 to n do begin
if s[i] = t[j] then cost := 0
else cost := 1;
if flip then
buf[j] := min3((buf[cuthalf + j] + 1),
(buf[j - 1] + 1),
(buf[cuthalf + j - 1] + cost))
else
buf[cuthalf + j] := min3((buf[j] + 1),
(buf[cuthalf + j - 1] + 1),
(buf[j - 1] + cost));
end;
flip := not flip;
end;
if flip then Result := buf[cuthalf + n]
else Result := buf[n];
end;
end;
← →
Dimedrol © (2005-12-13 15:22) [10]Verg !
Большое спасибо за код!
Я тут поискал по сети на "fuzzy search", и думаю что именно FUZZY -
это то что мне больше поможет.
Т.к. при вычислении Функции Левенштейна, иногда в очень похожих
строчках нужно сделать довольно большое кол-во изменений,
чтобы преобразовать одно в другое.
Думаю, что "Левенштейн" больше подходит для устранения ошибок
набора.
В моем случае - это немного другое.
Дело в том, что мне нужно выявить (и показать администратору)
дубликаты объявлений, поданных на сайт.
Ну или очень похожие объявления, т.к. хитро-попых ребят везде хватает. :-)
Для большей ясности - привожу свой код (FreePas, Delphi...)-
program sym;
{$MODE OBJFPC}
uses
SysUtils;
Type
TRetCount = record
lngSubRows : integer;
lngCountLike : integer;
end;
var r:integer;
function ReplaceChars(CString: PChar;scr: PChar;dest: PChar):PChar;
var i,j:integer;
begin
i:=0;
while (CString[i]<>#0) do
begin
j:=0;
while (scr[j]<>#0) do
begin
if CString[i]=scr[j]
then
begin
CString[i]:=dest[j];
Break;
end;
inc(j);
end;
inc(i);
end;
result:=CString;
end;
function MyUpper(src:PChar): PChar;
const small_chars:PChar="abcdefghijklmnopqrstuvwxyzабвгдеёжзийклмнопрстуфхцчшщъыьэюяў¤¦є°іµљЅї";
big_chars:PChar= "ABCDEFGHIJKLMNOPQRSTUVWXYZАБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯЎЈҐЄ¬ЇІґЉјѕ";
begin
Result:=ReplaceChars(src,small_chars,big_chars);
end;
function Matching(StrInputA: String;
StrInputB: String;
lngLen: Integer) : TRetCount;
Var
TempRet : TRetCount;
PosStrB : Integer;
PosStrA : Integer;
StrA : String;
StrB : String;
StrTempA : String;
StrTempB : String;
p1,p2:pchar;
begin
StrA := StrInputA;
StrB := StrInputB;
TempRet.lngCountLike:=0; TempRet.lngSubRows:=0;
For PosStrA:= 1 To Length(strA) - lngLen + 1 do
begin
StrTempA:= Copy(strA, PosStrA, lngLen);
PosStrB:= 1;
For PosStrB:= 1 To Length(strB) - lngLen + 1 do
begin
StrTempB:= Copy(strB, PosStrB, lngLen);
p1:=StrAlloc(length(StrTempA)+1);
StrPCopy (P1, StrTempA);
p2:= StrAlloc(length(StrTempB)+1);
StrPCopy (P2, StrTempB);
if string(MyUpper(p1))=string(MyUpper(p2)) then
begin
Inc(TempRet.lngCountLike);
break;
end
end;
Inc(TempRet.lngSubRows);
end; // PosStrA
Matching.lngCountLike:= TempRet.lngCountLike;
Matching.lngSubRows := TempRet.lngSubRows;
end; { function }
//------------------------------------------------------------------------------
function IndistinctMatching(MaxMatching : Integer;
strInputMatching: String;
strInputStandart: String): Integer;
Var
gret : TRetCount;
tret : TRetCount;
lngCurLen: Integer ; //текущая длина подстроки
begin
//если не передан какой-либо параметр, то выход
If (MaxMatching = 0) Or (Length(strInputMatching) = 0) Or
(Length(strInputStandart) = 0) Then
begin
IndistinctMatching:= 0;
exit;
end;
gret.lngCountLike:= 0;
gret.lngSubRows := 0;
// Цикл прохода по длине сравниваемой фразы
For lngCurLen:= 1 To MaxMatching do
begin
//Сравниваем строку A со строкой B
tret:= Matching(strInputMatching, strInputStandart, lngCurLen);
gret.lngCountLike := gret.lngCountLike + tret.lngCountLike;
gret.lngSubRows := gret.lngSubRows + tret.lngSubRows;
//Сравниваем строку B со строкой A
tret:= Matching(strInputStandart, strInputMatching, lngCurLen);
gret.lngCountLike := gret.lngCountLike + tret.lngCountLike;
gret.lngSubRows := gret.lngSubRows + tret.lngSubRows;
end;
If gret.lngSubRows = 0 Then
begin
IndistinctMatching:= 0;
exit;
end;
IndistinctMatching:= Trunc((gret.lngCountLike / gret.lngSubRows) * 100);
end;
//------------------------------------------------------------------------------
begin
r:=IndistinctMatching(4,
"PLOTNIKI Regips-Steny,potolki,peregorodki.Poly.",
"STROITELI Plotniki:-Regips-Steny,potolki,peregorodki.Poly."
);
if r > 40 then writeln("Strings are seems to be match, with similarity=",r,"%") else writeln("Strings NOT match. Similarity=",r,"%");
end.
Пожалуйста не обращайте внимания на неоптимизированность некоторых функций (замены символов и т.п.). У меня есть и более оптимизированный вариант, но в принципе - производительность не повысилась "на порядок".
Так вот, берем для сравнения 2 строки (уже в translite для удобства)
"PLOTNIKI Regips-Steny,potolki,peregorodki.Poly.",
и
"STROITELI Plotniki:-Regips-Steny,potolki,peregorodki.Poly."
Это - 2 объявления от строителей. Похожи, не правда ли ?!
Так вот, мой алгоритм выдает следующий результат:
c:\FreePas\dima\Textmatch>sym
Strings are seems to be match, with similarity=88%
По-моему - все логично.
Но! "Левенштейн" в данном случае выдает значение = 17 !
Много это или мало ?!
Трудно сказать.
Конечно же на примере:
Мама мыла раму
и
Мама мыла рому
"Левенштейн" "скажет" = 1.
Но как раз дело в том, что у меня могут быть разные объявы и по словам
и по длине и т.п.
Мне показалось, что Функция Левенштейна здесь не совсем подходит.
Может у кого-то есть пример FUZZY search ?
← →
TUser © (2005-12-13 15:26) [11]
> Т.к. при вычислении Функции Левенштейна, иногда в очень
> похожих
> строчках нужно сделать довольно большое кол-во изменений,
>
> чтобы преобразовать одно в другое.
Эээ, откуда такое мнение?
← →
Jeer © (2005-12-13 16:15) [12]Dimedrol © (13.12.05 15:22) [10]
Копай в сторону семантического распознавания текста, т.е. смыслового.
Но это на нобелевскую потянет.
Можно и проще - путем сравнения с оригиналом, по-словно, определяй "похожесть".
Но это может быть очень далеко от аналогичного смысла, выраженной иными словами.
В общем, сначала - теория.
Ищи - "компоненты языковой системы".
← →
Jeer © (2005-12-13 16:19) [13]Пример:
«ехать», «идти», «плыть», «лететь» объединены признаком «передвижение человека» и противопоставлены друг другу признаком «способ передвижения»
И в контексте "объявления" могут быть использованы любые их сочетания, тем не менее, правильно понимаемые читающим это объявление.
← →
Jeer © (2005-12-13 16:22) [14]1. "Продается славянский шкаф, недорого".
2. "Имеем возможность предложить старинный платяной шкаф, гарантированно не мусульманского дизайна. Цена - ниже возможной в любом ином месте.
← →
Dimedrol © (2005-12-13 18:41) [15]Не не не !!!
Ребята !!!
Все не так страшно!
Никакой нобелевской премии!
У меня уже есть(!!!) работающий алгоритм!
Проверьте его сами.
И делает он то что надо!
Только не быстро.
Мне советовали FUZZY search!
Говорят - то что надо - "нечеткий поиск".
Страницы: 1 вся ветка
Форум: "Основная";
Текущий архив: 2006.01.15;
Скачать: [xml.tar.bz2];
Память: 0.52 MB
Время: 0.013 c