Поиск повторов коде

← →
QAZ (2010-08-17 13:12) [0]

есть ли утилита эксперт по даному вопросу
нужно не сравнение файлов
а поиск в одном файле

← →
Игорь Шевченко © (2010-08-17 13:46) [1]

найдешь поделись

← →
Alx2 © (2010-08-17 14:01) [2]

Повторы интересны семантические, или как повторяющаяся подстрока кода без whitespace? Если второе - то элементарно пишется самостоятельно :)
Если первое - [1] :)

← →
QAZ (2010-08-17 14:17) [3]

> семантические

семанчто?

← →
Alx2 © (2010-08-17 14:40) [4]

>QAZ (17.08.10 14:17) [3]

То бишь по-смыслу (т.е. генерят один и тот же результат на одинаковых данных).

К примеру, два семантически одинаковых куска:
----------------
var sum, N, idx : integer;
begin
sum := 0;
N:=100;
for idx := 1 to N do
inc(sum,idx);
-----------

----------------
var
acc, k : integer;
S : cardinal;
acc := 0;
S := 100;
for k := 1 to S do
acc:=acc+k;
-----------

← →
QAZ (2010-08-17 14:47) [5]

неее
это ты загнул
просто повторы без пробелов,табов, коментариев
хотябы

← →
Alx2 © (2010-08-17 15:06) [6]

Тогда чистим от whitespace и
http://algolist.manual.ru/search/lrs/index.php

простой алгоритм, работающий "в среднем" за время O(n * ln (n)) с такой идеей:

Берем строку, считаем каждую позицию в ней началом новой строки, непрерывно продолжающейся до конца исходной строки. Сортируем эти строки. Затем попарно в них ищем одинаковые участки, начиная с первых позиций. Обнаруженные участки и будут дублями.

← →
QAZ (2010-08-17 17:15) [7]

буть другом,напиши а?

← →
Alx2 © (2010-08-18 09:31) [8]

>QAZ (17.08.10 17:15) [7]

Сорри. Работа, семья...

← →
12 © (2010-08-18 11:28) [9]

http://algolist.manual.ru/search/lrs/index.php
похоже на Левинштейна чем-то первый алгоритм (самый простой)

только строка получится ТАКАЯ..

2 кб исходника модуля
2048х2048 = 4 194 304 байт в матрице

а если серьезные тексты брать?!..

← →
Alx2 © (2010-08-18 11:34) [10]

>12 © (18.08.10 11:28) [9]

Да, наивный вариант непрактичный.
Но вполне просто сделать с расходом памяти O(n). ([6])

← →
12 © (2010-08-18 11:46) [11]

> Но вполне просто сделать с расходом памяти O(n). ([6])

т.е.

мамаЙЙЙмылаЙЙЙраму
амаЙЙЙмылаЙЙЙраму
..
ЙЙЙмылаЙЙЙраму
..
ЙЙЙраму
..
му
у
------
сортируем,
ЙЙЙмылаЙЙЙраму
ЙЙЙраму
..

дальше?
Первую сравниваем со всеми?, Вторую со всеми и т.д?
А как сравнивать?

← →
Alx2 © (2010-08-18 12:19) [12]

Сравнивать только соседей. Потому-что все отсортировано

← →
Alx2 © (2010-08-18 12:35) [13]

Примерно так:

function getMaxRepeatedSubStr(const source: String):String;
var idxs: array of integer;

begin
//Заводим массив целых чисел с кол-вом элементов равным длние строки
setLength(idxs,Length(source));
// заполняем его номерами начал строк (то есть числами от 1 до lenght(source))
for k := 0 to length(Source)-1 do
idxs[k] := k+1;

// Сортируем массив idxs, где в кач-ве для сравнения используется примерно это:
idxs[k]>idxs[p] если source[idxs[k]]...source[length(source)-1] >source[idxs[p]]...source[length(source)-1]
Только функцию copy лучше не юзать. А использовать а-ля PChar

далее, после сортировки
Result := "";
for k := 1 to length(idxs)-1 do begin
commonPartStr := getCommonPart(idxs[k-1],idxs[k],source);
// commonPart(k1,k2,str) возвращает общий участок для подстрок из str, начинающихся с позиции k1 и k2
if length(Result)<Length(commonPartStr) then
Result :=commonPartStr;

end;

Result := bestResult;
end;

Вот, по памяти O(n), по времени, в худшем случае O(n^2), а в лучшем - в районе O(n*log(n)), где n - длина строки

Ну и + дальнейша мегаоптимизация, которая позволит свести к линейному варианту (фактически, к суффиксным деревьям)

Эх, оставил атавизм: Result := bestResult; :)

Да, еще вот что: сравнивать только соседей достаточно потому, что после сортировки строки с одинаковыми началами буду соседями. И чем одинаковей начала - тем соседистей строки.

> сравнивать только соседей достаточно потому, что после сортировки
> строки с одинаковыми началами буду соседями. И чем одинаковей
> начала - тем соседистей строки.

верно!
меня это смущало поначалу

> Игорь Шевченко © (18.08.10 13:04) [17]

не понял
или так

руками, по алгоритму [6], по шагам, прямо в браузер набивал :)

12 © (18.08.10 13:38) [18]

Нет смысла сравнивать абстрактные строки в вакууме. Есть смысл сранивать синтаксические конструкции

Поиск повторов коде Найти похожие ветки