Версия для печати темы

Нажмите сюда для просмотра этой темы в обычном формате

Форум «Всё о Паскале» _ Задачи _ Поиск одинаковых строк в двух файлах

Автор: *оля* 24.04.2010 19:21

А если нужно сравнить 2 текстовых файла и вывести номера строк, которые совпадают, можно использовать этот алгоритм? и если да, то как?

Автор: Lapp 25.04.2010 7:51

Цитата(*оля* @ 24.04.2010 16:21) *
сравнить 2 текстовых файла и вывести номера строк, которые совпадают
Уточни, пожалуйста: совпадающие строки в разных файлах могут иметь разные номера (например: строка 2 файла 1 и строка 5 файла 2 совпадают), или речь идет о совпадении строк на одной и той же позиции (типа строка 2 в файлах одинаковая)?

Автор: Romtek 26.04.2010 0:51

Цитата(*оля* @ 24.04.2010 16:21) *

А если нужно сравнить 2 текстовых файла и вывести номера строк, которые совпадают, можно использовать этот алгоритм? и если да, то как?
Нужно использовать алгоритм Diff. Поищи в интернете.

Автор: *оля* 26.04.2010 1:28

Цитата(Lapp @ 25.04.2010 3:51) *

Уточни, пожалуйста: совпадающие строки в разных файлах могут иметь разные номера (например: строка 2 файла 1 и строка 5 файла 2 совпадают), или речь идет о совпадении строк на одной и той же позиции (типа строка 2 в файлах одинаковая)?


совпадающие строки в разны файлах могут иметь разные номера.

Автор: Lapp 26.04.2010 10:33

Цитата(*оля* @ 25.04.2010 22:28) *
совпадающие строки в разны файлах могут иметь разные номера.
Гым wacko.gif .
Самое естественное в этой ситуации с моей точки зрения - отсортировать оба файла (сохранив информацию о первоначальных положениях строк) в лексикографическом порядке (скажем, по возрастанию), потом пройтись по ним параллельно и найти, что требуется. Работы полно, короче. С самого начала - неясно, как сортировать: в создавать копию файла или считывать в массив и там орудовать? Первый способ медленный, второй может потребовать много памяти. Что скажешь?

Автор: *оля* 26.04.2010 22:02

Цитата(Lapp @ 26.04.2010 6:33) *

Гым wacko.gif .
Самое естественное в этой ситуации с моей точки зрения - отсортировать оба файла (сохранив информацию о первоначальных положениях строк) в лексикографическом порядке (скажем, по возрастанию), потом пройтись по ним параллельно и найти, что требуется. Работы полно, короче. С самого начала - неясно, как сортировать: в создавать копию файла или считывать в массив и там орудовать? Первый способ медленный, второй может потребовать много памяти. Что скажешь?


мда, все оказывается не так просто...
Насчет того, что может потребовать много памяти или будет медленнее работать, это не важно, лишь бы работала)
Да, и вправду, логично сначала отсортировать, а потом сравнивать, правда, не совсем уверена, что все хорошо получится, во всяком случае у меня))

Автор: *оля* 27.04.2010 0:51

а можно просто каждую строку первого файла поочередно сравнить со всеми строками второго?

Автор: volvo 27.04.2010 1:21

Можно, конечно... Как говорила героиня одного фильма "Можно и зайца научить курить" (С). Представляешь, сколько лишних действий ты сделаешь, если будешь постоянно туда-сюда бегать по файлу?

Ты лучше скажи, у тебя файлы большие, или не очень?

Автор: *оля* 27.04.2010 1:28

Цитата(volvo @ 26.04.2010 21:21) *

Можно, конечно... Как говорила героиня одного фильма "Можно и зайца научить курить" (С). Представляешь, сколько лишних действий ты сделаешь, если будешь постоянно туда-сюда бегать по файлу?

Ты лучше скажи, у тебя файлы большие, или не очень?

smile.gif да, я понимаю, но просто не знаю уже как сделать.
ну вообще подразумеваются не маленькие, а что от этого зависит?

Автор: Client 27.04.2010 1:40

Цитата
а что от этого зависит?
Думаю что время выполнения и объем ресурсов.

Автор: *оля* 27.04.2010 13:16

Цитата(Client @ 26.04.2010 21:40) *

Думаю что время выполнения и объем ресурсов.


ну тогда это не столь важно, главное получить результат

Автор: volvo 27.04.2010 13:28

Да поймите же наконец, что ресурсы компьютера ограничены!!!

*оля*
Ну, напишешь ты программу, которая будет читать строки из файлов в массивы и работать с ними (либо сортировать оба массива, как предлагал Lapp, либо отсортировать один, и потом бинарным поиском искать в нем строки из второго - не суть важно). Это будет прекрасно работать на маленьких файлах, скажем, по 200 строк. А попытаешься обработать файл из 1000 строк таким образом - что будет? А ничего - вылет из программы с сообщением о нехватке памяти... Это тебе нужно?

Так что определяй, что значит "не маленькие". И озвучь, наконец, каким ты компилятором пользуешься. То, что может один компилятор - для другого может оказаться неприемлемым.

Автор: Lapp 27.04.2010 13:50

Цитата(*оля* @ 26.04.2010 22:28) *
ну вообще подразумеваются не маленькие, а что от этого зависит?
Работоспособность.

Цитата(Client @ 26.04.2010 22:40) *
Думаю что время выполнения и объем ресурсов.
Нет, Client. В некоторый момент сумка может порваться, лодка затонуть, селезенка надорваться. нет смысла говорить о "выполнении", если на него требуются годы (или даже дни) либо память 100 Гиг..

Автор: *оля* 27.04.2010 14:10

ну вообще, в задаче подразумевалось сравнивать файлы до 1500 строк, но если это реализовать слишком сложно, то можно задачу упростить, скажем, ввести заранее ограничение, пусть будет работать только для небольших файлов.
программы нам разрешают писать только в PascalABC или PascalABC.net

Автор: Lapp 27.04.2010 14:34

Цитата(*оля* @ 27.04.2010 11:10) *
ну вообще, в задаче подразумевалось сравнивать файлы до 1500 строк, но если это реализовать слишком сложно, то можно задачу упростить, скажем, ввести заранее ограничение, пусть будет работать только для небольших файлов.
1500 - это как раз вполне терпимо. Если компилятор 32-разрядный, то можно и в памяти сделать.

Цитата
программы нам разрешают писать только в PascalABC или PascalABC.net
А вот это для меня лично, например, непреодолимое препятствие.. Из-за этого устанавливать эту лабуду я не буду ((. Я использую FPC. Про алгоритм можно продолжать разговоры, но все адаптации к ABC, если они потребуются - сама, пожалуйста. Устраивает?

Оля, я разделяю тему. В следующий раз, пожалуйста, создавай свою тему, а не пость в чужие.

Автор: *оля* 27.04.2010 14:52

Цитата(Lapp @ 27.04.2010 10:34) *

1500 - это как раз вполне терпимо. Если компилятор 32-разрядный, то можно и в памяти сделать.

А вот это для меня лично, например, непреодолимое препятствие.. Из-за этого устанавливать эту лабуду я не буду ((. Я использую FPC. Про алгоритм можно продолжать разговоры, но все адаптации к ABC, если они потребуются - сама, пожалуйста. Устраивает?

Оля, я разделяю тему. В следующий раз, пожалуйста, создавай свою тему, а не пость в чужие.


ок, в следующий раз буду создавать свою тему)

конечно устраивает!)
главное, хотя бы определиться, как все-таки сравнивать. Нашла статью, в которой сравнивают 2 файла с помощью арифметического кодирования строк числами с плавающей запятой. Но там по-моему все еще сложнее... вроде как расписан алгоритм, но не совсем понятно.

Автор: Lapp 27.04.2010 15:09

Цитата(*оля* @ 27.04.2010 11:52) *
Нашла статью, в которой сравнивают 2 файла с помощью арифметического кодирования строк числами с плавающей запятой. Но там по-моему все еще сложнее... вроде как расписан алгоритм, но не совсем понятно.
А чем не нравится мой алгоритм?

Автор: volvo 27.04.2010 15:32

Оля,
да если у тебя есть возможность использовать PascalABC.NET - там делать нечего... Берешь файл. Один... Построчно читаешь его в переменную типа String, и запоминаешь в List<String> ее хеш. Любой. Скажем, MD5 (с использованием System.Security.Cryptography он вычисляется в 3 строки). А потом открываешь второй файл, и опять же построчно читаешь, вычисляешь для прочитанной строки тот же хеш, и ищешь его в списке.

"Всего и делов то..." (С) "Осенний марафон"

Автор: *оля* 27.04.2010 16:59

Цитата(Lapp @ 27.04.2010 11:09) *

А чем не нравится мой алгоритм?


не, не в том дело, что он не нравится, просто я не знаю как его реализовать

Добавлено через 10 мин.
Цитата(volvo @ 27.04.2010 11:32) *

Построчно читаешь его в переменную типа String, и запоминаешь в List<String> ее хеш. Любой. Скажем, MD5 (с использованием System.Security.Cryptography он вычисляется в 3 строки).



что-то я не совсем поняла как это сделать(((

Автор: Lapp 27.04.2010 17:10

Цитата(*оля* @ 27.04.2010 13:59) *
не, не в том дело, что он не нравится, просто я не знаю как его реализовать
а алгоритм volvo? Что в нем неясного?

Для некоторого упрощения: можно просто читать каждую строку из первого файла искать ее во втором.

Автор: *оля* 27.04.2010 17:39

Цитата(Lapp @ 27.04.2010 13:10) *

а алгоритм volvo? Что в нем неясного?

Для некоторого упрощения: можно просто читать каждую строку из первого файла искать ее во втором.


Скажем, MD5 (с использованием System.Security.Cryptography он вычисляется в 3 строки).
вот это не понятно мне

Автор: volvo 27.04.2010 17:56

Ну смотри. Существует такой алгоритм хеширования - http://ru.wikipedia.org/wiki/MD5

Так вот, подобный хеш можно получить из любой строки, используя доступные из PascalABC.NET ДотНет-овские классы, а не писать функции для его вычисления самостоятельно:

uses 
  System.Collections.Generic, System.Security.Cryptography;

var
  prov:System.Security.Cryptography.MD5CryptoServiceProvider; 
  // это надо будет еще проинициализировать в основной программе
  
function CalcHash(s: string):string;
var
  a: array of byte;
  sb: System.Text.StringBuilder;
begin
  a := System.Text.Encoding.UTF8.GetBytes(s);
  a := prov.ComputeHash(a);
  sb := new System.Text.StringBuilder;
  foreach b: byte in a do sb.Append(b.ToString('x2').ToLower());

  CalcHash:= sb.ToString;
end;
В результате функция вернет хеш переданной в нее строки, который будет уникальным. Совпадение хешей будет означать совпадение строк, для которых они вычислялись.

Но это - уже реализация. Что в алгоритме-то непонятно? smile.gif

Автор: *оля* 27.04.2010 20:45

Цитата(volvo @ 27.04.2010 13:56) *

Ну смотри. Существует такой алгоритм хеширования - http://ru.wikipedia.org/wiki/MD5
...
Но это - уже реализация. Что в алгоритме-то непонятно? smile.gif


smile.gif теперь все понятно, спасибо! во всяком случае пока, сейчас попробую написать полностью программу, тогда думаю возникнут еще вопросы по мере написания)

Автор: *оля* 28.04.2010 1:16

выдает такую ошибку: Ошибка времени выполнения: В экземпляре объекта не задана ссылка на объект.
в строке
a := prov.ComputeHash(a);
я наверное что-то не дописала...что бы это могло быть?

Автор: volvo 28.04.2010 1:21

А я предупреждал:

Цитата
// это надо будет еще проинициализировать в основной программе


В самом начале основной программы надо инициализировать этот объект:
prov := new System.Security.Cryptography.MD5CryptoServiceProvider;

, только после этого его можно использовать. Обрати внимание, точно так же перед использованием внутри функции инициализируется System.Text.StringBuilder. Любой обзект перед тем, как к нему обращаться, нужно создать...

Автор: *оля* 28.04.2010 1:33

точно, написано же было, забыла. спасибо, теперь все нормально пока)

Автор: Lapp 28.04.2010 16:13

2 volvo:
я все же не понимаю, в чем тут пойнт применения хэшей. Почему нельзя сравнивать сами строки? В задаче нет ничего про секьюрити или там сжатие.. Сравнение строк может быть эффективнее использования хэшей в конечном итоге. Большинство строк начинаются с неравных символов - они сразу отметаются в самом начале. А для вычисления хэша всегда нужно прочитать всю строку. Зачем? blink.gif

Автор: volvo 28.04.2010 16:24

Только ради экономии памяти. Прочитать все строки файла в память (а строка может быть длинной), или хранить только хеш (фиксированной, причем небольшой) длины - это две большие разницы. И разницы эти тем больше, чем больше размеры файлов, с которыми нужно работать и чем длиннее в них строки.

В принципе, можно обойтись и без хеширования, конечно; надо будет прогнать пару тестов на больших файлах, посмотреть, насколько быстро MD5 вообще вычисляется, и насколько программа начинает подтормаживать, когда ей проходится работать со строками, а не их хешами... Если торможения не будет (или будет незначительное) - то работать с полными строками.

Автор: Lapp 28.04.2010 16:32

Цитата(volvo @ 28.04.2010 13:24) *
Только ради экономии памяти.
да, про память я как-то уже забыл тут.. smile.gif Прикинул, что 1500 строк (по максимум 255 символов) берут не больше трети мега - и забыл..

Да, конечно, если нужно сжимать - то хэш. Но, судя по началу темы ("лишь бы работало")) - скорее всего не нужно.. Сравнить скорость двух подходов: с хэшированием и непосредственным чтением из файла - это действительно интересно. Результат, впрочем, будет сильно зависеть от системного дискового кэша..

Автор: *оля* 28.04.2010 21:14

идея сравнить 2 метода очень интересная good.gif )))

Автор: *оля* 28.04.2010 22:30

Цитата(volvo @ 27.04.2010 11:32) *

Берешь файл. Один... Построчно читаешь его в переменную типа String, и запоминаешь в List<String> ее хеш.



можно спросить, каким образом сохранить в List<String>? (

Автор: volvo 28.04.2010 22:41

У него есть метод Add:

var
  L: System.Collections.Generic.List<string>;

... 
  // Инициализируем список:
  L := new System.Collections.Generic.List<string>;

  // Каким-то образом получаем строку, которую надо сохранить (назовем ее st)

  L.Add(st); // и заносим строку в список

За дополнительной информацией о .NET-овских контейнерах - сюда: http://msdn.microsoft.com/en-us/library/0sbxh9x2%28v=VS.100%29.aspx

Автор: *оля* 28.04.2010 23:51

Цитата(volvo @ 28.04.2010 18:41) *

У него есть метод Add:
var
  L: System.Collections.Generic.List<string>;

... 
  // Инициализируем список:
  L := new System.Collections.Generic.List<string>;

  // Каким-то образом получаем строку, которую надо сохранить (назовем ее st)

  L.Add(st); // и заносим строку в список



а потом,для поиска тоже свой метод есть?

Автор: volvo 29.04.2010 1:47

Естественно. Есть метод Find, есть FindAll (для поиска всех совпадений по заданному критерию), есть метод Contains, позволяющий определить просто есть ли в списке заданный элемент, есть IndexOf (чтобы определить индекс элемента, совпадающего с искомой строкой)... Методов - валом...

Мне кажется, или тема уже вышла далеко за рамки раздела "Задачи"? Теперь здесь в основном обсуждаются .NET-овские фишки. Может перенести в "Другие языки"? (я понимаю, что язык тот же, но... Туда и шарписты заходят, может помогут чем).

Автор: *оля* 30.04.2010 2:24

Цитата(volvo @ 28.04.2010 21:47) *

Естественно. Есть метод Find, есть FindAll (для поиска всех совпадений по заданному критерию), есть метод Contains, позволяющий определить просто есть ли в списке заданный элемент, есть IndexOf (чтобы определить индекс элемента, совпадающего с искомой строкой)... Методов - валом...

Мне кажется, или тема уже вышла далеко за рамки раздела "Задачи"? Теперь здесь в основном обсуждаются .NET-овские фишки. Может перенести в "Другие языки"? (я понимаю, что язык тот же, но... Туда и шарписты заходят, может помогут чем).


спасибо, все, с .NET-овскими фишками вопросов больше нет)
теперь другое... мы считаем хеш сразу для всей строки, а как посчитатеь его не сразу для всей, а для каждого слова в строке отдельно?

Автор: *оля* 30.04.2010 22:39

что не так в программе? 

 var
rand8: array[0..255] of integer;
st: string;
line: string;
F: text;
f_name: string;

procedure init;
var
i: integer;
begin
randomize;
for i:=0 to 255 do
rand8[i]:=random(255);
end;

function h(st: string): integer;
Var
Sum: longint;
I: integer;
Begin
For i:=0 to length(st) do
Sum := sum + ord(st[i]) xor rand8[i];
H:=sum mod 256;
end;

begin
writeln('введите имя файла');
readln(f_name);
assign(f,f_name);
reset(f);
while not eof(f) do begin
readln(line);
st:=line;
init;
h(st);
writeln (h(st));
end;
close(f);
end.
.

Автор: *оля* 30.04.2010 23:28

все, нашла ошибку, сорри