Сравнение текстов

← →
George © (2011-07-28 09:26) [0]

Встала задача - сравнить тексты на схожесть (выявление плагиата). Сначала я хотел применить нагугленный мной алгоритм шинглов (http://habrahabr.ru/blogs/algorithm/65944/), но потом оказалось, что надо еще и подсвечивать схожие участки текста и генерировать по ним отчет, а проверка алгоритмом шинглов не выявляет похожих мест, она лишь вычисляет процент схожести. Есть какие-то другие решения или идеи, как это реализовать?

← →
oldman © (2011-07-28 09:40) [1]

если текст отличается хоть на запятую, это не плагиат.
на адвокатах разоришься.

вот такие "решения и идеи"

← →
George © (2011-07-28 09:44) [2]

> oldman © (28.07.11 09:40) [1]

Да не, вопрос с адвокатами там не стоит. Т.е. людям нужно оценивать похожесть "входящих" текстов с теми, что уже есть. В зависимости от этой похожести принимать определенные меры (отказ в публикации, еще что-нибудь). Для чего нужен отчет - компьютер может говорить, что тексты похожи, тогда в этом случае уже должен проверить оператор.

← →
SQLEXPRESS (2011-07-28 10:18) [3]

Имхо, нет нормального для русского языка алгоритма.
Или он будет более-менее приемлем, за неприемлемое время

Забавно, в одном из сервисов
Два окна ввода, скопировал в одно их же шапку
Сравнение осуществляется по собственным алгоритмам с целью расчета наибольшей схожести текстов. Алгоритмы поисковых систем могут намного отличаться от используемых нами.

Скопировал в другое и подвигал слова
По собственным алгоритмам мы осуществляем сравнение наибольшей схожести текстов с целью расчета плагиата.
Алгоритмы всех поисковых систем намного могут отличаться от используемого нами алгоритма.

На сколько схожесть потянет? Процентов на 80-90?
Схожесть: 44.44%
моя в шоке, менее половины..

← →
George © (2011-07-28 10:23) [4]

Надо от языка абстрагироваься - сравниваться будут тексты на русском, английском и казахском языках. Т.е. видимо просто по словам сравнивать. Но, блин, как?

← →
SQLEXPRESS (2011-07-28 10:24) [5]

Шинглы

Введите в верхнее поле исходный текст, а в нижнее измененный и нажмите "Проверить". В результате вы получите процент схожести по 4 проверкам, каждая из которых соответствует определенному количеству слов в шингле.

Введите в нижнее поле измененный текст, а в верхнее поле введите исходный текст. Нажмите "Проверить". Результатом будет процент их схожести сделанный по 4 проверкам. Каждая из проверок будет соответствать определенному кол-ву слов в разных шинглах.

Количество слов в шингле - 1. Процент схожести - 54.05%
Количество слов в шингле - 2. Процент схожести - 25.49%
Количество слов в шингле - 3. Процент схожести - 8.77%
Количество слов в шингле - 4. Процент схожести - 3.45%

← →
George © (2011-07-28 10:24) [6]

Еще момент. Можно было бы как-нибудь тупо сравнить, но там один текст сравнивается с десятью тысячами других, к примеру. Поэтому скорость - важный фактор.

← →
George © (2011-07-28 10:25) [7]

> SQLEXPRESS (28.07.11 10:24) [5]

Я в том сервисе смотрел исходники, там недоработанный алгоритм шинглов. Поэтому и точность не ахти.

← →
SQLEXPRESS (2011-07-28 10:37) [8]

> Надо от языка абстрагироваься

не получится

в английском - I love you. И все.
Love I you и I you love - не скажешь. А в русском - запросто.

> Т.е. видимо просто по словам сравнивать. Но, блин, как?

я как то делал, правда, только с единичными предложениями.
И задача стояла проще - рекламу сгруппировать по смыслу и прибить группами.
(C)тырено откуда то

procedure TMDIChild.btn1Click(Sender: TObject);
begin
ShowMessage( IntToStr( IndistinctMatching(4, "папа у Васи силен в математике", "у Васи папа в математике не слаб") ) );
end;

function Matching(StrInputA: WideString;
StrInputB: WideString;
lngLen: Integer): TRetCount;
var
TempRet: TRetCount;
PosStrB: Integer;
PosStrA: Integer;
StrA: WideString;
StrB: WideString;
StrTempA: WideString;
StrTempB: WideString;
begin
StrA := string(StrInputA);
StrB := string(StrInputB);

for PosStrA := 1 to Length(strA) - lngLen + 1 do
begin
StrTempA := System.Copy(strA, PosStrA, lngLen);

PosStrB := 1;
for PosStrB := 1 to Length(strB) - lngLen + 1 do
begin
StrTempB := System.Copy(strB, PosStrB, lngLen);
if SysUtils.AnsiCompareText(StrTempA, StrTempB) = 0 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: WideString;
strInputStandart: WideString): 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;

← →
George © (2011-07-28 10:57) [9]

Да реализацию не надо, спасибо. Мне для веба это надо, там не на дельфи будет. )
Мне бы направление. Я вот сейчас думаю о том, как бы алгоритмом шинглов реализовать с возможностью подсветки.

← →
TUser © (2011-07-28 11:04) [10]

Поиск локально сходных участков осуществляется алгоритмом смита-ватермана. Если кратко, то в интернете можно найти алгоритм Левенштейна, а у СВ - такое же динамическое программирование, но

1. выбирается максимум из 0 или суммы по предыдущему пути
2. среднее значение матрицы весов должно быть меньше нуля

Если надо подробнее - я могу скинуть литературу (мыло в анкете). У меня есть то, что касается сравнения последовательностей ДНК и белков, но для произвольного текста оно тоже подойдет.

← →
Чайник © (2011-07-28 11:04) [11]

> Мне бы направление. Я вот сейчас думаю о том, как бы алгоритмом
> шинглов реализовать с возможностью подсветки.

Разбить текст на абзацы, сравнивать поабзацно. Подсвечивать тот абзац, где процент наибольший.

← →
SQLEXPRESS (2011-07-28 11:13) [12]

> алгоритм Левенштейна

тоже делал, но там вроде как для слов только

алгоритм такой

function LevenshteinDistance(s, t: string):integer;
var
d: array [0..50, 0..50] of integer; // good number 50, if sub 4 and div 46 - eq 1 :)
i,j:integer;
m,n:integer;
begin
m:=length(s);
n:=length(t);
for i := 0 to m do d[i, 0] := i; // deletion
for j := 0 to n do d[0, j] := j; // insertion
for j := 1 to n do
begin
for i := 1 to m do
begin
if s[i] = t[j] then
d[i, j] := d[i-1, j-1]
else
d[i, j] := min
(d[i-1, j] + 1, // deletion
d[i, j-1] + 1, // insertion
d[i-1, j-1] + 1 // substitution
)
end;
end;
Result := d[m,n];
end;

function DamerauLevenshteinDistance(s, t: string):integer;
var
d: array [0..50, 0..50] of integer; // good number 50, if sub 4 and div 46 - eq 1 :)
i,j,cost:integer;
m,n:integer;
begin
m:=length(s);
n:=length(t);
for i := 0 to m do d[i, 0] := i; // deletion
for j := 0 to n do d[0, j] := j; // insertion
for j := 1 to n do
begin
for i := 1 to m do
begin
if s[i] = t[j] then cost := 0
else cost := 1;
d[i, j] := min(d[i-1, j ] + 1, // deletion
d[i , j-1] + 1, // insertion
d[i-1, j-1] + cost // substitution
);
if (i > 1)
and (j > 1)
and (s[i] = t[j-1])
and (s[i-1] = t[j]) then
d[i, j] := min( 9999,
d[i, j],
d[i-2, j-2] + cost // transposition
);
end;
end;
Result := d[m,n];
end;

> проверка алгоритмом шинглов не выявляет похожих мест

Что мешает его модифицировать?
Просто вместе с минимальным хешем хранишь его позицию.

> Просто вместе с минимальным хешем хранишь его позицию.

Ну вот этот вариант у меня родился в голове после создания темы. Единственная сложность, которую я вижу - у них сейчас есть готовое решение, там показывается два абзаца, которые сравниваются и в обоих подсвечены одинаковые слова. Т.е. подсвечивать совпадающий десяток слов вроде как не кошерно, пока не могу придумать, как обойти.

> подсвечивать совпадающий десяток слов вроде как не кошерно, пока не могу придумать, как обойти

распространить подсветку совпадащих слов
влево-вправо от найденного места.

Сравнение текстов Найти похожие ветки