Сравнение и выделение различий в текстовых строках: реализация алгоритмов Diff в Delphi и Pascal для SynEdit.

Delphi , Синтаксис , Текст и Строки

Введение
Сравнение текстовых строк с визуальным выделением различий — распространённая задача в разработке редакторов кода, систем контроля версий и инструментов анализа данных. В этой статье мы рассмотрим практические подходы к реализации этой функциональности в среде Delphi и Lazarus с использованием компонента SynEdit, а также предложим готовые решения с примерами кода на Object Pascal.

Проблема сравнения строк

При сравнении двух строк недостаточно простого побайтового сравнения — необходимо точно определить позиции расхождений и визуализировать их. Рассмотрим пример:

Строка 1: 'This is a nice day, the sky is blue and wind blowing sun is rising.'
Строка 2: 'This is a nice day with many kills, the sky is red and wind blowing sun is somewhere, because all dark here.'

Требуется выделить различия на уровне символов или слов. Основные сложности:
1. Определение минимального набора изменений
2. Поддержка Unicode-символов
3. Интеграция с компонентами редактора (SynEdit)

Алгоритмы сравнения текста

1. Longest Common Subsequence (LCS)

Алгоритм поиска наибольшей общей подпоследовательности хорошо подходит для сравнения текстов.

uses 
  SysUtils, Math;

function LCSLength(const X, Y: string): Integer;
var
  C: array of array of Integer;
  i, j: Integer;
begin
  SetLength(C, Length(X) + 1, Length(Y) + 1);
  for i := 0 to Length(X) do C[i,0] := 0;
  for j := 0 to Length(Y) do C[0,j] := 0;

  for i := 1 to Length(X) do
    for j := 1 to Length(Y) do
      if X[i] = Y[j] then
        C[i,j] := C[i-1,j-1] + 1
      else
        C[i,j] := Max(C[i,j-1], C[i-1,j]);

  Result := C[Length(X), Length(Y)];
end;

2. Алгоритм Майерса (Myers Diff)

Более эффективный алгоритм с оптимальной асимптотикой O(ND), где N — сумма длин строк, D — количество различий.

Реализация сравнения с поддержкой Unicode

Для корректной работы с Unicode необходимо использовать WideString и учитывать особенности кодировок.

{$mode delphiunicode}

uses
  SysUtils, Classes;

type
  TDiffKind = (dkNone, dkAdd, dkDelete, dkModify);

  TDiffItem = record
    Kind: TDiffKind;
    StartOld,
    EndOld,
    StartNew,
    EndNew: Integer;
  end;

function ComputeDiffs(const OldStr, NewStr: WideString): TArray<TDiffItem>;
var
  // Реализация алгоритма сравнения
begin
  // ... (подробная реализация опущена для краткости)
end;

Интеграция с SynEdit

Для визуализации различий в SynEdit необходимо создать кастомную разметку:

type
  TSynDiffMarkup = class(TSynEditMarkup)
  private
    FDiffs: TArray<TDiffItem>;
  protected
    procedure Paint; override;
  public
    procedure SetDiffs(const ADiffs: TArray<TDiffItem>);
  end;

procedure TSynDiffMarkup.Paint;
var
  i: Integer;
  StartPos, EndPos: TPoint;
begin
  for i := 0 to High(FDiffs) do
  begin
    if FDiffs[i].Kind = dkAdd then
    begin
      StartPos := Point(FDiffs[i].StartNew, Line);
      EndPos := Point(FDiffs[i].EndNew, Line);
      Canvas.Brush.Color := clGreen;
      Canvas.FrameRect(Bounds(StartPos.X, StartPos.Y, EndPos.X - StartPos.X, LineHeight));
    end;
    // Аналогично для других типов изменений
  end;
end;

Полный пример реализации

Рассмотрим решение с использованием модифицированной библиотеки TextDiff с поддержкой Unicode:

uses
  Diff, Graphics, SynEdit;

procedure HighlightDiffs(SynEdit: TSynEdit; const OldText, NewText: string);
var
  Diff: TDiff;
  i: Integer;
begin
  Diff := TDiff.Create(nil);
  try
    Diff.Execute(OldText, NewText);

    SynEdit.BeginUpdate;
    try
      SynEdit.Lines.Text := NewText;
      for i := 0 to Diff.Count - 1 do
      begin
        case Diff.Compares[i].Kind of
          ckAdd:
            SynEdit.SetHighlightColor(
              Diff.Compares[i].OldIndex1, 
              Diff.Compares[i].OldIndex2, 
              clGreen);
          ckDelete:
            SynEdit.SetHighlightColor(
              Diff.Compares[i].OldIndex1, 
              Diff.Compares[i].OldIndex2, 
              clRed);
          ckModify:
            SynEdit.SetHighlightColor(
              Diff.Compares[i].OldIndex1, 
              Diff.Compares[i].OldIndex2, 
              clBlue);
        end;
      end;
    finally
      SynEdit.EndUpdate;
    end;
  finally
    Diff.Free;
  end;
end;

Решение проблем с Unicode

Для корректной обработки UTF-8 и UTF-16:
1. Всегда используйте {$mode delphiunicode}
2. Преобразуйте строки в WideString перед сравнением
3. Учитывайте Surrogate пары при работе с UTF-16

function UTF8ToWideCustom(const S: UTF8String): WideString;
begin
  Result := UTF8Decode(S);
end;

Альтернативные подходы

1. Использование LGenerics:

uses
  lgSeqUtils;

var
  Diffs: TStringDiff;
begin
  Diffs := ComputeStringDiff('строка1', 'строка2');
  // Обработка различий
end;

1. Внешние библиотеки:
2. TextDiff (требует доработки для Unicode)
3. LazUtils - содержит различные утилиты сравнения

Оптимизация производительности

1. Кэширование результатов сравнения
2. Использование битовых масок для быстрого сравнения
3. Параллельные вычисления для больших текстов

// Пример параллельного сравнения
uses
  System.Threading;

procedure ParallelDiff(const List1, List2: TStringList);
var
  Diffs: TArray<TDiffItem>;
begin
  TTask.Run(procedure
    begin
      Diffs := ComputeDiffsParallel(List1.Text, List2.Text);
      TThread.Synchronize(nil, procedure
        begin
          ApplyDiffsToSynEdit(Diffs);
        end);
    end);
end;

Заключение

Сравнение текстовых строк с выделением различий в Delphi и Pascal требует понимания алгоритмов сравнения и особенностей работы с Unicode. Реализация на основе алгоритма Майерса или LCS в сочетании с кастомной разметкой SynEdit предоставляет гибкое и эффективное решение. Предложенные примеры кода могут служить основой для создания продвинутых инструментов сравнения текстов в ваших приложениях.

Дальнейшие улучшения:
1. Добавление поддержки сравнения с учётом регистра
2. Реализация "fuzzy" сравнения для нечёткого поиска различий
3. Интеграция с системой контроля версий
4. Оптимизация для работы с большими файлами

Используя приведённые в статье подходы, вы сможете реализовать мощный инструмент для сравнения текстов, адаптированный под ваши конкретные требования.

Создано по материалам из источника по ссылке.

Практическое руководство по реализации алгоритмов сравнения текста с визуализацией различий в компоненте SynEdit для Delphi/Pascal с поддержкой Unicode и примерами кода.

Комментарии и вопросы

Получайте свежие новости и обновления по Object Pascal, Delphi и Lazarus прямо в свой смартфон. Подпишитесь на наш Telegram-канал delphi_kansoftware и будьте в курсе последних тенденций в разработке под Linux, Windows, Android и iOS

:: Главная :: Текст и Строки ::