Консультация № 187315
06.05.2013, 09:44
96.03 руб.
0 20 0
Здравствуйте, уважаемые эксперты! Прошу вас ответить на следующий вопрос:

Среда - Delphi5 (в крайнем случае Delphi7, но не желательно).

Входное условие:

Есть две строки
Строка1:
123456,456789,9548,ААвв,FFrrR
Строка2:
123856,456789,9548,АБвв,FУrrR

Как получить "результирующую" строку - в чем их отличие, как это сделано в Total Commander - Файлы / сравнить по содержимому?

Ответ должен быть "по идее":
Строка1:
123456,456789,9548,ААвв,FFrrR
Строка2:
123856,456789,9548,АБвв,FЮrrR

Насколько я понимаю тут надо как то использовать регулярные выражения, но я увы в них совсем не силен...
И главное как "ограничить" количество искомых ошибок, в смысле если их скажем более 5-7, то это уже совсем разные строки...

P.S. Никаких сторонних компонентов не использую... нельзя нам их ставить...
P.P.S. Почему такая "устарелла" - Delphi5 - потому что лицензионная...
P.P.P.S. Выделение цветом будет в RichEdit, впрочем это не важно, наверное...

В общем прошу помощи господа эксперты!

Обсуждение

давно
Профессионал
153662
1070
06.05.2013, 11:04
общий
06.05.2013, 11:05
На ум приходит сравнение по символам, если текущий символ не совпадает, то выводим его другим цветом, заодно считаем количество несовпадающих символов. Пока нет времени реализовать в делфи, да и 5 версии нет, только 7 и турбоделфи. Да вот забыл, у меня есть программа для сравнения файлов, делал в 7 версии, может подойти, если подкорректировать и убрать скины.
Прикрепленные файлы:
0b265c6697ddc63fa37c3c3e4d68a9b6.rar
Об авторе:
Мои программы со статусом freeware для Windows на моём сайте jonix.ucoz.ru

Неизвестный
06.05.2013, 11:44
общий
Адресаты:
Посимвольно это решение "в лоб" - будет работать ну очень долго и медленно... такое написать действительно не сложно (такое я сам могу - это задача для школьника...).

Ведь понятное дело, что сравниваю я не одну строку с одной строкой... а 2000 с 2000...
7ка, теоретически подойдет, только нужен код, а не программа.

(на самый крайний случай подойдет даже Delphi XE2, лишь бы это было быстро... т.е. если более 5(7) далее не сравнивать... но посимвольно... это будет катастрофа, полагаю...)
давно
Профессионал
153662
1070
06.05.2013, 11:56
общий
Вот мой код этой программы, если файлы одинаковые, то на их сравнение уходит 5 сек на 4000 строк, если есть отличие прога останавливается на этой строке, жмём далее:
Код:
unit sravFal;

interface

uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, sSkinProvider, sSkinManager, StdCtrls, Buttons, ComCtrls,
ExtCtrls, Gauges;

type
TForm1 = class(TForm)
BitBtn1: TBitBtn;
BitBtn2: TBitBtn;
BitBtn3: TBitBtn;
BitBtn4: TBitBtn;
sSkinManager1: TsSkinManager;
sSkinProvider1: TsSkinProvider;
RichEdit1: TRichEdit;
RichEdit2: TRichEdit;
OpenDialog1: TOpenDialog;
BitBtn6: TBitBtn;
StatusBar1: TStatusBar;
BitBtn5: TBitBtn;
Label1: TLabel;
Label2: TLabel;
Label3: TLabel;
Label4: TLabel;
ProgressBar1: TProgressBar;
Label5: TLabel;
Label6: TLabel;
procedure FormResize(Sender: TObject);
procedure BitBtn1Click(Sender: TObject);
procedure BitBtn2Click(Sender: TObject);
procedure BitBtn6Click(Sender: TObject);
procedure BitBtn3Click(Sender: TObject);
procedure FormCreate(Sender: TObject);
procedure BitBtn4Click(Sender: TObject);
procedure BitBtn5Click(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;

var
Form1: TForm1; i:Integer; a: byte;

implementation

{$R *.dfm}

procedure TForm1.FormResize(Sender: TObject);
begin
RichEdit1.Width:= Form1.Width div 2 - 10;
RichEdit2.Left:= RichEdit1.Width + 8;
RichEdit2.Width:= RichEdit1.Width;
StatusBar1.Panels[0].Width:= Form1.Width - 160;
ProgressBar1.Width:= StatusBar1.Panels[0].Width - 8;
end;

procedure TForm1.BitBtn1Click(Sender: TObject);
begin
RichEdit1.Perform(EM_LIMITTEXT, $7FFFFFF0, 0);
If not OpenDialog1.Execute then exit;
RichEdit1.Lines.LoadFromFile(OpenDialog1.FileName);
ProgressBar1.Max:= RichEdit1.Lines.Count;
Label1.Caption:= IntToStr(RichEdit1.Lines.Count);
end;

procedure TForm1.BitBtn2Click(Sender: TObject);
begin
RichEdit2.Perform(EM_LIMITTEXT, $7FFFFFF0, 0);
RichEdit2.Font.Color:= clBlack;
RichEdit2.DefAttributes.Color:= clBlack;
If not OpenDialog1.Execute then exit;
RichEdit2.Lines.LoadFromFile(OpenDialog1.FileName);
Label6.Caption:= IntToStr(RichEdit2.Lines.Count);
end;

procedure TForm1.BitBtn6Click(Sender: TObject);
begin
Close;
end;

procedure TForm1.BitBtn3Click(Sender: TObject);
var j: Word; l: Integer; s, s1, ch1, ch2: String;
begin
with Richedit1 do
begin
Selstart := perform(EM_LINEINDEX, 0, 0);
SelLength:= Length(RichEdit1.Lines.Strings[0]);
perform(EM_SCROLLCARET, 0, 0);
end;
with Richedit2 do
begin
Selstart := perform(EM_LINEINDEX, 0, 0);
SelLength:= Length(RichEdit2.Lines.Strings[0]);
perform(EM_SCROLLCARET, 0, 0);
end;
StatusBar1.Panels[1].Text:='Идёт сравнение, ждите';
i:= 0;
l:= RichEdit1.Lines.Count;
Label1.Caption:= IntToStr(l);
Label6.Caption:= IntToStr(RichEdit2.Lines.Count);
s:= RichEdit1.Lines.Strings[i];
s1:= RichEdit2.Lines.Strings[i];
while s = s1 do
begin
If l = i then
begin
If a < 2 then
StatusBar1.Panels[1].Text:='Файлы одинаковы'
else
If a = 2 then
StatusBar1.Panels[1].Text:='Файлы отличаются';
Windows.Beep(500, 500);
with Richedit1 do
begin
Selstart := perform(EM_LINEINDEX, i, 0);
SelLength:= Length(RichEdit1.Lines.Strings[i]);
perform(EM_SCROLLCARET, 0, 0);
end;
with Richedit2 do
begin
Selstart := perform(EM_LINEINDEX, i, 0);
SelLength:= Length(RichEdit2.Lines.Strings[i]);
perform(EM_SCROLLCARET, 0, 0);
end;
exit;
end;
Inc(i);
s:= RichEdit1.Lines.Strings[i];
s1:= RichEdit2.Lines.Strings[i];
ProgressBar1.Position:= i;
Label2.Caption:= IntToStr(i);
Application.ProcessMessages;
end;
For j:=0 to Length(RichEdit1.Lines.Strings[i]) do
begin
ch1:= Copy(s, j, 1);
ch2:= Copy(s1, j, 1);
If ch1 <> ch2 then
begin
RichEdit2.SelStart := RichEdit2.Perform(EM_LINEINDEX, i, 0) + (j - 1);
Break;
end;
end;
with Richedit1 do
begin
Selstart := perform(EM_LINEINDEX, i, 0);
SelLength:= Length(RichEdit1.Lines.Strings[i]){ - j};
SelAttributes.Color:=clBlue;
perform(EM_SCROLLCARET, 0, 0);
end;
with Richedit2 do
begin
SelLength:= Length(RichEdit2.Lines.Strings[i]) - j + 1;
SelAttributes.Color:=clRed;
perform(EM_SCROLLCARET, 0, 0);
end;
StatusBar1.Panels[1].Text:='Строка отличается';
Windows.Beep(500, 250);
a:= 2;
end;

procedure TForm1.FormCreate(Sender: TObject);
begin
with ProgressBar1 do
begin
Parent := StatusBar1;
Top := 5;
Left := 4;
Height := StatusBar1.Height - 8;
Width := StatusBar1.Panels[0].Width - 8;
end;
PostMessage(ProgressBar1.Handle, $0409, 0, clGreen);
end;

procedure TForm1.BitBtn4Click(Sender: TObject);
var j: Word; l: Integer; s, s1, ch1, ch2: String;
begin
StatusBar1.Panels[1].Text:='Идёт сравнение, ждите';
l:= RichEdit1.Lines.Count;
Label1.Caption:= IntToStr(l);
Label6.Caption:= IntToStr(RichEdit2.Lines.Count);
Inc(i);
s:= RichEdit1.Lines.Strings[i];
s1:= RichEdit2.Lines.Strings[i];
l:= RichEdit1.Lines.Count;
while s = s1 do
begin
If l <= i then
begin
If a < 2 then
StatusBar1.Panels[1].Text:='Файлы одинаковы'
else
If a = 2 then
StatusBar1.Panels[1].Text:='Файлы отличаются';
Windows.Beep(500, 500);
with Richedit1 do
begin
Selstart := perform(EM_LINEINDEX, i, 0);
SelLength:= Length(RichEdit1.Lines.Strings[i]);
perform(EM_SCROLLCARET, 0, 0);
end;
with Richedit2 do
begin
Selstart := perform(EM_LINEINDEX, i, 0);
SelLength:= Length(RichEdit2.Lines.Strings[i]);
perform(EM_SCROLLCARET, 0, 0);
end;
exit;
end;
Inc(i);
s:= RichEdit1.Lines.Strings[i];
s1:= RichEdit2.Lines.Strings[i];
ProgressBar1.Position:= i;
Label2.Caption:= IntToStr(i);
Application.ProcessMessages;
end;
For j:=0 to Length(RichEdit1.Lines.Strings[i]) do
begin
ch1:= Copy(s, j, 1);
ch2:= Copy(s1, j, 1);
If ch1 <> ch2 then
begin
RichEdit2.SelStart := RichEdit2.Perform(EM_LINEINDEX, i, 0) + (j - 1);
Break;
end;
end;
with Richedit1 do
begin
Selstart := perform(EM_LINEINDEX, i, 0);
SelLength:= Length(RichEdit1.Lines.Strings[i]){ - j};
SelAttributes.Color:=clBlue;
perform(EM_SCROLLCARET, 0, 0);
end;
with Richedit2 do
begin
SelLength:= Length(RichEdit2.Lines.Strings[i]) - j;
SelAttributes.Color:=clRed;
perform(EM_SCROLLCARET, 0, 0);
end;
StatusBar1.Panels[1].Text:='Строка отличается';
Windows.Beep(500, 250);
a:= 2;
end;

procedure TForm1.BitBtn5Click(Sender: TObject);
begin
i:= RichEdit1.Lines.Count;
ProgressBar1.Position:= ProgressBar1.Max;
end;

end.
Об авторе:
Мои программы со статусом freeware для Windows на моём сайте jonix.ucoz.ru

Неизвестный
06.05.2013, 12:09
общий
Адресаты:
Это здорово... но они еще и НЕ по порядку.
Т.е. строки в файлах в разных местах...
Иными словами приходится брать первую строку и сравнивать со всеми 2000.
Потом вторую и опять с 2000...
Представляете сколько времени уйдет посимвольно?
Уфф.
Всё таки мне кажется это действительно быстро решается регулярными выражениями...
По крайней мере отбор "нужных" строк, а потом Ваш алгоритм для раскраски...
давно
Профессионал
153662
1070
06.05.2013, 12:17
общий
Тогда надо думать и время для этого, я пока не могу Вам помочь.
Об авторе:
Мои программы со статусом freeware для Windows на моём сайте jonix.ucoz.ru

Неизвестный
06.05.2013, 13:34
общий
Адресаты:
Жаль, буду ждать еще идей...

Ваш запустил... он показывает НАЧАЛО изменений в строке, а не отличающиеся данные, так что его в любом случае надо полностью переделывать :(.

Но всё равно СПАСИБО!

P.S. Хмм может как нибудь через Код символа и что нибудь из теории матриц применить ... Гауса того же...
давно
Профессионал
153662
1070
06.05.2013, 13:48
общий
Цитата: 5994
он показывает НАЧАЛО изменений в строке, а не отличающиеся данные,
Я так и задумывал для своих нужд.
Об авторе:
Мои программы со статусом freeware для Windows на моём сайте jonix.ucoz.ru

Неизвестный
06.05.2013, 15:58
общий
Есть такая идейка: если нужно сравнить между собой множество строк в файле, то для начала их можно упорядочить (сохранить в другом файле), а уже потом сравнивать между собой соседние. Регулярные выражения, по сути, так же породят цикл посимвольной обработки, так что существенного ускорения ожидать трудно.

Вечером могу попробовать плотно заняться Вашим вопросом. Если интерес есть - отпишитесь до 18 часов (по Москве).
Неизвестный
07.05.2013, 09:20
общий
Для решения задачи поставленной в вопросе, кроме посимвольного перебора врядли что-то еще можно придумать.
А для быстрого сравнения строк, может быть попробовать использовать некую хэш функцию, которая для похожих строк (отличающихся не более чем 5-7 символами) дает близкий результат, затем посчитать хэши всех строк и сравнивать уже их, а для "похожих", по результатам сравнения, строк использовать уже посимвольный перебор.
Неизвестный
07.05.2013, 10:32
общий
Вот это уже более менее хорошая идея.
А что подразумевается под "хэш строки" и как его подсчитать?
(Вариант полного посимвольного сравнения всех строк из одного файла с другим рассматривать не надо - слишком долго.)
Неизвестный
07.05.2013, 10:36
общий
ВАриант с "отсортировать" строки... мне кажется тоже не получится, так как получается, необходимо заводить некие таблицы огромного размера в памяти а "сортировка" строк в которых более 300 символов... так же будет очень долго, представьте ДВА файла по 2000 строк на 300 символов, мне кажется не реальная задача.
Неизвестный
07.05.2013, 10:52
общий
Имею ввиду некое преобразование строк в числа, такое чтобы получаемые числа тем меньше различались, чем меньше различий в исходных строках. (Например, самое простое - сложить все коды символов в строке, хотя такое преобразование не учитывает позиции сомволов и наверное даст очень большое число срабатываний).
Вообщем над формой преобразования надо подумать (сейчас на работе - пока некогда, попробую вечером помозговать), или попробовать поискать в литературе нечто подобное. Например, что-то типа "алгоритмов быстрого сравнения строк".
Неизвестный
07.05.2013, 12:15
общий
Хорошо, спасибо.
Неизвестный
07.05.2013, 18:41
общий
Цитата: 271861
попробовать использовать некую хэш функцию, которая для похожих строк (отличающихся не более чем 5-7 символами) дает близкий результат

Любопытная задумка, вот только в голову не приходит ни одной идеи, как такую функцию реализовать. Если просто сложить коды всех символов, то совершенно разные строки могут дать близкие суммы, тогда как разница сумм для похожих строк может оказаться более заметной. Учёт позиции заметно усложняет ситуацию: при неудачном выборе алгоритма один различающийся символ, находящийся на "сильной" позиции, даст куда больший вклад в общую оценку, чем несколько других, но на "слабых" местах. Кроме того по условиям задачи нет разницы, насколько различаются соответствующие символы разных строк: две соседние буквы (т.е. символы с близкими кодами) должны давать такой же вклад в оценку, как и литеры из разных языковых наборов.
Неизвестный
08.05.2013, 09:10
общий
Да условие задачи понято верно...
Если бы было просто я бы не пошел к вам за советом .
Меня смущает один тонкий момент, который надо добавить к условию задачи - строки в файлах как правило один к одному. Т.е. в беспорядке, но одной строке из одного файла соответствует одна строка в другом.
А если по "хэш" функции ... можно получить один ко многим...? Впрочем... это не страшно, можно будет сделать вывод типа:

Файл 1 строка1 100% нахождения не найдено, найдены ТРИ похожих:

Файл 2 строка561 (отличие 1 символ)
Файл 2 строка5 (отличие 3 символа)
Файл 2 строка78 (отличие 5 символов)

Анализируйте...

Осталось написать такую функцию и проверить на практике...
Но что-то меня всё таки смущает... в частности строки с пропущенными символами"выпадут" наверное, а такое естественно тоже исключать нельзя. Собственно поэтому я и думал про регулярки...
давно
Мастер-Эксперт
425
4118
14.05.2013, 06:08
общий
Если тема ещё актуальна.
Среди простых функций хэширования строк интернет предлагает алгоритм Пирсона:
- берётся числовое значение каждого символа строки и проводится операция XOR с каким-либо ключём.
Ещё можно найти в инете какую-нибудь функцию хэширования, например, подсчёт CRC или MD5. В Delphi 7, я знаю, в модуле httpd.pas были функции по расчёту MD5. Есть ли такой модуль в Delphi 5 я не знаю.
Об авторе:
Я только в одном глубоко убеждён - не надо иметь убеждений! :)
Неизвестный
14.05.2013, 11:09
общий
Адресаты:
Да акутально, хотя вопрос закрылся без ответа :(.

Цитата: Вадим Исаев ака sir Henry
какую-нибудь функцию хэширования
ага яндекс найдется всё... не находится.

Цитата: Вадим Исаев ака sir Henry
например, подсчёт CRC или MD5
Спасибо, попробую через MD5 сам написать, но что-то мне подсказывает что в случае пропущенных букв это будет не "айс".

Хммм....
Неизвестный
17.05.2013, 07:09
общий
Поразмыслив и поискав информацию пришел вот к каким выводам:
Кажется что хеширование стандартными функциями здесь врядли подойдет - они могут дать близкий результат для "разных" строк и очень далекий для похожих. Хотя можеть быть тут я не прав.
Накопал в интернете, что есть такое понятие, как "расстояние редактирования" между строками - сколько элементарных операций (удаление, добавление, перенос символа) нужно совершить чтобы одну строку преобразовать в другую. Как раз то что нужно, но алгоритмы для его определения нетривиальны и для массового сравнения строк вряд-ли сгодятся. Из этой же области "расстояние Хэмминга" - в скольких позициях отличаются одинаковые строки, к сожалению не нашел алгоритмов его определения.
При изучении информации пришла в голову мысль, использовать в качестве "хэш-функции" какой-либо код, применяемый в передаче информации для коррекции ошибок и посчитать для каждой строки контрольные значения порождаемые данным кодом, потом их сравнивать. Но дальше уже знаний не хватает к сожалению: существуют ли коды с коррекцией 5-7 ошибок, и если да, то сколько контрольных разрядов нужно для строки, например, в 255 символов? Реально ли их "впихнуть" в скажем 32 бита?
Вот так как-то. Дальше искать уже нет возможности.
Неизвестный
17.05.2013, 09:14
общий
Спасибо Дмитрий!

Цитата: 271861
Дальше искать уже нет возможности.
И не надоглавное идея.

Про "расстояние Хэмминга" и "расстояние редактирования" я не знал, действительно интересная область - буду изучать, хотя бы понятно стало в каком направлении "рыть".

Еще раз СПАСИБО!
Неизвестный
17.05.2013, 09:23
общий
Не за что.
Вам спасибо за вопрос - тоже много интересного узнал о нечетком сравнении строк.
Форма ответа