Почему LCS алгоритм находит совпадение в конце последовательности?
Если у меня есть две последовательности «ABC» и «ABCABCABC», то моя реализация LCS-алгоритма находит совпадение в последней части более длинной строки, а не в первой. Это общее свойство этого алгоритма или у меня что-то неправильно реализовано?
Проклятье, у меня не хватает знаний, чтобы верно задать вопрос. :(
Алгоритм реализовал несколько лет назад, просто переписал из какой-то чужой реализации. В любом случае, буду рад, если кто-нибудь что-нибудь подскажет.
В зависимости от реализации (порядок проверок, приоритет при совпадении длин) алгоритм действительно может искать самую последнюю или самую первую подпоследовательность.
Wataru, мне надо, чтобы находил совпадение в начале. Для решения прикладной задачи. Если находит в конце, это ломает мне алгоритм. Попытаюсь разобраться.
Антон Жучков, Наверно, что-то не так в вашем внешнем алгоритме. А что если самая длинная последовательность на конце? А последовательность на 1 короче - в самом начале?
Давайте вашу всю задачу, возможно тут надо не LCS вообще.
Если все же вам нужна первая LCS, то надо просто чуть-чуть модифицировать ваш алгоритм. Там, наверняка, где-то в цикле ищется максимальное число и вот там надо знаки правильно посавить (переписывать только если текущее значение строго больше пока найденого максимума).
// строим матрицу
for I := 0 to aCountLeft-1 do
begin
for J := 0 to aCountRight-1 do
begin
if aCompareFunc(I,J) then
PutAt(I,J, GetAt(I-1, J-1) + 1)
else
PutAt(I,J, Max(GetAt(I, J-1), GetAt(I-1, J)));
end;
end;
А потом строю diff:
procedure DoDiff(aL, aR: Integer);
begin
if (aL >= 0) and (aR >= 0) and aCompareFunc(aL, aR) then
begin
DoDiff(aL-1, aR-1);
aReportProc(RR(l3diffSame, aL, aR));
end
else
if (aR >= 0) and ((aL < 0) or (GetAt(aL, aR-1) >= GetAt(aL-1, aR))) then
begin
DoDiff(aL, aR-1);
aReportProc(RR(l3diffAdded, aL, aR));
end
else
if (aL >= 0) and ((aR < 0) or (GetAt(aL, aR-1) < GetAt(aL-1, aR))) then
begin
DoDiff(aL-1, aR);
aReportProc(RR(l3diffDeleted, aL, aR));
end;
end;
Что касается полной задачи, то мне надо именно что найти фрагмент текста в начале большого куска текста. Сравнение нечёткое, потому что большой кусок — это распознанный из картинки текст и нужно найти соответствие его и уже существующего.
Антон Жучков, Вот как раз хотел спросить, а что делать в случае "abcd" и "cdba" - тут есть 2 варианта взять наибольшее LCS размером в 2, но оно или в первой строке раньше, или во второй. Значит у вас надо именно минимизировать вхождение в первой строке.
Ваша рекурсия восстонавливает ответ в динамическом программировании в матрице.
Построение матрицы менять не надо, оно просто считает оптимальную длину LCS. Вам надо отдавать приоритет переходам вверх (или влево) пока это возможно при восстановлении ответа.
Но можно сделать простой хак - усеките ваш текст как можно короче, пока LCS все еще оптимального размера.
Вам надо найти самое первое максимальное число в последней строке (или столбце, в зависимости от того в какой из входных строчек вы хотите как можно левее найти вхождение. Я не в курсе, что у вас за aCompareFunc).
От этой позиции и запускайте ваш DoDiff вместо левой нижней ячейки матрицы.
Значения максимума даже не надо искать, он будет в левом нижнем углу матрицы. Вам остается только циклом найти самое левое число в строке (столбце) равное последнему.
Вам еще придется в конце зарепортить необходимое количество l3diffDeleted или l3diffAdded, чтобы восстановить усеченную часть.
Средний