Данная статья рассказывает о том как выделить различия в двух текстах, вроде того, как это делает svn. Допустим, у нас есть текст (начальный текст):
aa bb cc dd ee ff
и его модифицированная копия (Измененный текст):
aa bb xx cc dx ee
и нам нужно выделить различия. Алгоритм решения этой задачи следующий: 1) каждой строке присвоим уникальное имя (индекс), чтобы проше было работать составим таблицу:
aa 1
bb 2
cc 3
dd 4
ee 5
ff 6
xx 7
dx 8
2) теперь переведем строки согласно этой таблице:
aa bb cc dd ee ff => 1 2 3 4 5 6
aa bb xx cc dx ee => 1 2 7 3 8 5
3) далее используем специальный алгоритм - Алгоритм выбора наибольшей общей последовательности (longest common subsequence, LCS). Пока не будем разбираться как он работает. Среди наших строк:
Строка 1 1 2 3 4 5 6
Строка 2 1 2 7 3 8 5
Результат: 1 2 3 5
1 2 3 5 - самая длинная общая часть (эта часть одинакова с учетом, что где-то что-то вставили, где-то удалили)
4) далее поочередно просматриваем обе строки, и если, скажем, в одной строке символ появился, а в другой нет, значит он был вставлен и т.д.
1 строка 2 строка общая часть рез-тат сравнения
1 1 1 общий
2 2 2 общий
3 7 3 7 помечаем как вставленную и "сдвигаем" 2-ю строку вверх
3 3 3 общий
4 8 5 не общий, так как нет в общей строке - значит помечаем как измененную, т.к. в общей строке не совпало то в ней не переходим на след. символ, а в остальных переходим
5 5 5 общий
6 т.к. есть в 1-ой, а во второй нет - удаленная
5) теперь выделив все что было нужно просто заменяем индентификаторы реальными строчками из уникальной таблицы, которую получили в 1-ом пункте и получаем конечный результат.
Код программы выполняющей эти действия:
function GetLCSAlgoritm(&$_a, &$_b) {
$a = explode(" ",$_a);
$b = explode(" ",$_b);
$maxLen = array();
for($i=0, $x=count($a); $i<=$x; $i++) {
$maxLen[$i] = array();
for($j=0, $y=count($b); $j<=$y; $j++) $maxLen[$i][$j] = '';
}
for($i=count($a)-1; $i>=0; $i--) {
for($j=count($b)-1; $j>=0; $j--) {
if($a[$i] == $b[$j]) $maxLen[$i][$j] = 1+$maxLen[$i+1][$j+1];
else $maxLen[$i][$j] = max($maxLen[$i+1][$j],$maxLen[$i][$j+1]);
}
}
$rez = "";
for($i=0, $j=0; $maxLen[$i][$j]!=0 && $i<$x && $j<$y;) {
if($a[$i] == $b[$j]) {
$rez .= $a[$i]." ";
$i++;
$j++;
}
else {
if($maxLen[$i][$j] == $maxLen[$i+1][$j]) $i++;
else $j++;
}
}
return trim($rez);
}
function GetUnickStr(&$arr, &$arrUnick) {
$s='';
$arrUnickFlip = array_flip($arrUnick);
foreach($arr as $v) {
$s .= $arrUnickFlip[$v].' ';
}
return trim($s);
}
function FromUnickToArr(&$arrStr, &$arrUnick) {
$r = array();
foreach($arrStr as $v) {
$buff = array();
$buff[] = $arrUnick[$v[0]];
$buff[] = $v[1];
$r[] = $buff;
}
return $r;
}
function SelDiffsStr(&$_a, &$_b, &$retA, &$retB) {
$_longest = GetLCSAlgoritm($_a,$_b);
$longest = explode(" ",$_longest);
$a = explode(" ",$_a);
$b = explode(" ",$_b);
$rB = array();
$i1 = 0; $i2 = 0;
for($i=0, $iters = count($b); $i<$iters; $i++) {
$simbol = array();
if(isset($longest[$i1]) && $longest[$i1] == $b[$i2]) {
$simbol[] = $longest[$i1];
$simbol[] = "*";
$rB[] = $simbol;
$i1++;
$i2++;
}
else {
$simbol[] = $b[$i2];
$simbol[] = "+";
$rB[] = $simbol;
$i2++;
}
}
$retB = $rB;
$i1 = 0; $i2 = 0;
for($i=0,$iters = count($a); $i<$iters; $i++) {
$simbol = array();
if(isset($longest[$i1]) && $longest[$i1] == $a[$i2]) {
$simbol[] = $longest[$i1];
$simbol[] = "*";
$rA[] = $simbol;
$i1++;
$i2++;
}
else {
$simbol[] = $a[$i2];
$simbol[] = "-";
$rA[] = $simbol;
$i2++;
}
}
$retA = $rA;
}
function SelDiffsText(&$aText, &$bText, &$retAText, &$retBText) {
$arrA = str_replace("\r","",$aText);
$arrB = str_replace("\r","",$bText);
$arrA = explode("\n",$arrA);
$arrB = explode("\n",$arrB);
$unickTable = array_unique(array_merge($arrA,$arrB));
$strA = GetUnickStr($arrA,$unickTable);
$strB = GetUnickStr($arrB,$unickTable);
SelDiffsStr($strA,$strB,$retA,$retB);
$retAText = FromUnickToArr($retA,$unickTable);
$retBText = FromUnickToArr($retB,$unickTable);
}
function SelDiffsColor(&$rdyAText, &$rdyBText, &$strRetA, &$strRetB) {
$strRetA = "";
$strRetB = "";
foreach($rdyAText as $v) {
if($v[1] == "+") $strRetA.='<font color="#00cc33">'.$v[0].'</font>';
elseif($v[1] == '-') $strRetA.='<font color="#7c7b7c"><s>'.$v[0].'</s></font>';
elseif($v[1] == 'm') $strRetA.='<font color="#e64444">'.$v[0].'</font>';
elseif($v[1] == '*') $strRetA.=$v[0];
}
foreach($rdyBText as $v) {
if($v[1] == "+") $strRetB.='<font color="#00cc33">'.$v[0].'</font>';
elseif($v[1] == '-') $strRetB.='<font color="#7c7b7c"><s>'.$v[0].'</s></font>';
elseif($v[1] == 'm') $strRetB.='<font color="#e64444">'.$v[0].'</font>';
elseif($v[1] == '*') $strRetB.=$v[0];
}
}
function MergeInsertAndDelete(&$rdyAText, &$rdyBText) {
$max = count($rdyAText)>count($rdyBText)?count($rdyAText):count($rdyBText);
for($i1=0,$i2=0; $i1<$max && $i2<$max; ) {
if($rdyAText[$i1][1]=="-" && $rdyBText[$i2][1]=="+" && $rdyBText[$i2][0]!="") {
$rdyAText[$i1][1]="*";
$rdyBText[$i2][1]="m";
}
elseif($rdyAText[$i1][1]!="-" && $rdyBText[$i2][1]=="+") $i2++;
elseif($rdyAText[$i1][1]=="-" && $rdyBText[$i2][1]!="+") $i1++;
$i1++;
$i2++;
}
}
// ***********************************************************
// Main function
// ***********************************************************
// string $sA, $sB = strings where try find differences
// string $retA, $retB = strings for return result of work
function SelectedDiffs(&$sA, &$sB, &$retA, &$retB) {
SelDiffsText($sA,$sB,$retAText,$retBText);
MergeInsertAndDelete($retAText,$retBText);
SelDiffsColor($retAText,$retBText,$retA,$retB);
}
функции:
GetUnickStr(&$arr, &$arrUnick)
вход : массив слов текста, указатель на уникальную таблицу инлентификаторов (которую получаем ф-ей GetUnickTable)
выход: строка состаящая из индентификаторов взятых из таблицы уникальных индентификаторов
(ПУНКТ 2 получаем уникальные строки)
FromUnickToArr(&$arrStr, &$arrUnick)
вход : массив представляющий уникальную строку ($arrStr), массив уникальной таблицы индентификаторов ($arrUnick)
выход: массив являющийся обычным текстом.
GetLCSAlgoritm(&$_a, &$_b)
ф-я реализующая Алгоритм выделения наибольшей общей последовательности
вход : строка уникальный индентификаторов представляющая 1-ый текст($_a) и 2-ой текст ($_b)
выход: строка уникальных индентификаторов являющаяеся наибольшей общей последовательностью
(ПУНКТ 3 находим наибольшую общую последовательность)
В алгоритме строка разбивается построчно:
текст 1:
aaa bbb ccc == 1
ddd eee == 2
fff ggg == 3
а при перобразовании в строку индентификаторов цифры разделяюся пробелами : '1 2 3'
SelDiffsStr(&$_a, &$_b, &$retA, &$retB)
ф-я выдления изменений в строках индентификаторов
вход : $_a, $_b - строки индентификатров представляющие соответсвенно текстНачальный и текстИзмененный, $retA, $retB - указатели куда нужно вернуть результат - строки индентификаторов $_a и $_b только уже с выделениями
выход: выход организуется путем передачи указателей на параметры в которых сохранить результат
SelDiffsColor(&$rdyAText, &$rdyBText, &$strRetA, &$strRetB)
ф-я предназначена для выделения цветом (удаленный текст, вставленный текст, измененный текст)
MergeInsertAndDelete(&$rdyAText, &$rdyBText)
как говорилось в ПУНКТЕ 4, когда мы встретили ситуацию 4 8 5 - можно было либо сразу выделить текст как изменненый, либо так, что в 1-ой строке он был удален, а во второй вставлен, так вот у меня 2-ой вариант и потому я использую эту ф-ю, чтобы найти такие ситуации и выделить текст как измененный.
SelDiffsText(& $aText, & $bText, & $retAText, & $retBText)
ф-я выделения изменений в строках только уже текстов, а не индентификаторов, т.е. эта ф-я получает на вход тексты Начальный и Измененный, сама создает уникальную таблицу, переводит эти тексты в строки индентификаторов вызывает ф-ю SelDiffsText - для выделения различий в индентификаторах, а потом для получившихся результатов вызывает ф-ю FromUnickToArr при помощи которой строки индентификаторов переводит в обычный выделенный текст
SelectedDiffs(& $sA, & $sB, & $retA, & $retB)
главная ф-я которая объединяет все выше
вход:
$sA - текст Начальный
$sB - текст Измененный
$retA - указатель куда надо вернуть строку с выделенным цветами Начальным текстом
$retB - указатель куда надо вернуть строку с выделенный цветами Измененным текстом
выход: выход организуется путем передачи указателей на параметры в которых сохранить результат
пример:
начальный текст измененный текст
ф-я выделения изменений
в строках только уже текстов,
а не индентификаторов,
т.е. эта ф-я получает на вход тексты
Начальный и Измененный,
сама создает уникальную таблицу,
переводит эти тексты
ф-я выдiления изменений
в строках только уже текстов,
а не индентификаторов,
это новая строка
т.е. эта ф-я получает на вход тексты
сама создает уникальную таблицу,
переводит тексты
Алгоритм выделения наибольшей общей последовательности можно найти тут: wikipedia -
Алгоритм