Выделение различий в текстах (svn, diff)

Данная статья рассказывает о том как выделить различия в двух текстах, вроде того, как это делает 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.=''.$v[0].'';
		elseif($v[1] == '-') 	$strRetA.=''.$v[0].'';
		elseif($v[1] == 'm')	$strRetA.=''.$v[0].'';
		elseif($v[1] == '*')	$strRetA.=$v[0];
	}

	foreach($rdyBText as $v) {
		if($v[1] == "+")		$strRetB.=''.$v[0].'';
		elseif($v[1] == '-')	$strRetB.=''.$v[0].'';
		elseif($v[1] == 'm')	$strRetB.=''.$v[0].'';
		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 — Алгоритм

Михаил Зайцев

2 thoughts on “Выделение различий в текстах (svn, diff)

  1. В коде пропущены процедуры заполнения $rdyAText и $rdyBText. А идея хорошая. Давно искал реализацию. Спасибо.

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *