Печать Diff от самой длинной общей подпоследовательности

Question

Итак, я занимаюсь некоторыми проблемами с практикой для Perl & Python (выбор между двумя), и у меня возникла проблема, когда мне нужно создать собственный алгоритм дифференциации, как и у Github. Я до такой степени, что знаю, что самая длинная проблема общего подпоследовательности - большая часть решения. Я использовал wikipedia page for LCS в качестве справочной информации, но у меня все еще возникли проблемы с выяснением части diff.

Я также понимаю, что на CPAN уже есть модули, такие как Алгоритм: Diff, но это в основном только для практики, и они чувствуют себя обманом.

Я вычислил версию алгоритма python/псевдокода, но я планирую сделать это с помощью многомерных массивов, которые, по-видимому, нет в Perl.

Теперь я добрался до места, где я могу получить самую длинную общую длину подпоследовательности в Perl.

В основном псевдокод (почти питона-как, но, как предполагается, на Perl), я думаю, что-то вроде этого:

function lengthOfLCS(string1, string2){ 
    if length(string1) == 0 or length(string2) == 0: 
     return 0 
    else if string1[0] eq string2[0]: 
     return 1+ lengthOfLCS(stringA[1:], stringB[1:]) 
    return max(lengthOfLCS(string1, string2[1:], lengthOfLCS(string1[1:], string2)) 

я не выполнил его, но я думаю, что это в основном как я могу рассчитать длину LCS двух строк?

Выход мудр, он должен вернуть 4 против «HUMAN» & «Шимпанзе» (LCS = HMan)

Так что я спрашиваю, как мне добраться до типографских дифференциалы с помощью Perl с этого момента? Я знаю, что вместо длины LCS вместо этого я должен вернуть список/массив, что можно сделать, возвратив многомерный список в функции LCS, а затем обработать его позже в отдельной функции diff ,

Я новичок в Perl, поэтому любые указатели/советы были бы весьма признательны. Спасибо.

Answer 1

Вы можете использовать мою ссылочную реализацию LCS в Perl, которая нуждается в двух ссылках на массив в качестве входных данных и возвращает массив из двух массивов элементов, содержащих индексы соответствующих элементов.

use LCS; 
my $lcs = LCS->LCS([qw(a b)], [qw(a b b)]); 
# $lcs now contains an arrayref of matching positions 
# same as 
$lcs = [ 
    [ 0, 0 ], 
    [ 1, 2 ] 
]; 

LCS использует традиционный алгоритм и считывает LCS итеративно (см мой пост в блоге Loopify рекурсии в wollmers-perl.blogspot.de), то есть не рекурсивный (большинство образцов кодов используют рекурсии, которые не очень хорошо масштабируется в Perl). Поэтому, если вы хотите узнать из кода, посмотрите на subs LCS() и _lcs().

Если вам нужен diff, то есть скрипт редактирования, вы можете восстановить его из массива LCS.

Метод lcs2align() делает почти это.

use Data::Dumper; 
use LCS; 
print Dumper(
    LCS->lcs2align(
    [qw(a b)], 
    [qw(a b b)], 
    LCS->LCS([qw(a b)],[qw(a b b)]) 
) 
); 
# prints 
$VAR1 = [ 
      [ 
      'a', 
      'a' 
      ], 
      [ 
      '', 
      'b' 
      ], 
      [ 
      'b', 
      'b' 
      ] 
]; 

различий в формате SDiff() (see Algorithm::Diff) будет выглядеть так:

[ 
    [ 'u', 'a', 'a' ], 
    [ '+', '', 'b' ], 
    [ 'u', 'b', 'b' ], 
] 

Как получить редактировать сценарий из выравнивания должна быть тривиальной и оставляется в качестве упражнения.

Если вы хотите использовать более быструю реализацию, вы можете использовать LCS :: Tiny или самую быструю чистую реализацию Perl LCS :: BV или самую быструю для больших масштабов. Алгоритм :: Diff :: XS (см. Мой блог) Алгоритм настройки :: Diff на wollmers-perl.blogspot.de)

Обратите внимание, что сценарий редактирования на основе LCS автоматически не предоставляет SES (кратчайший скрипт редактирования). LCS основан на действиях редактирования, позволяющих вставлять и удалять (простое расстояние редактирования). Алгоритмы SES обычно минимизируют расстояние Левенштейна (вставка, удаление и несоответствие).