Nickolay.info. Алгоритмы. Самая длинная повторяющаяся цепочка значений в массиве |
Подобная задача часто возникает на практике, например, при подготовке данных к сжатию или выявлении статистических закономерностей в данных.
Требуется найти максимальную повторяющуюся подстроку в строке, на числовых данных ту же задачу можно понимать как поиск самого длинного "подмассива" из повторяющихся значений в массиве.
Как и большинство задач, решать можно или довольно просто, но с квадратичным (как минимум) ростом вычислительных затрат в зависимости от размерности данных, или несколько более экономично по вычислительным затратам, но головоломно с точки зрения программирования.
Естественный подход к решению задачи предполагает, что для выявления в массиве повторяющихся "цепочек" мы должны хотя бы сравнить
каждый элемент с каждым, то есть, понадобится алгоритм сложности не менее, чем N2/2. Действительно, за квадратичное
время решить задачу можно так: строится матрица M размерностью n*n, такая что
Mi,j = 1, если yi = yj, и Mi,j = 0 в противном случае. Если исключить главную диагональ,
все диагонали в матрице, состоящие из идущих подряд единиц, представляют собой позиции, в которых содержатся
максимальные повторяющиеся подстроки,
самая длинная из которых является искомой повторяющейся подстрокой. Поскольку матрица симметрична
относительно главной диагонали, достаточно вычислять и обрабатывать только элементы выше или ниже
главной диагонали, вот соответствующий код:
const size=100;
type
vector= array [1..size] of integer;
matrix= array [1..size,1..size] of integer;
var a:vector;
procedure fill (n:integer;var a:vector);
{Заполнение массива значениями 2-5 + вывод}
var i:integer;
begin
writeln;
for i:=1 to n do begin
a[i]:=2+random(4);
write (a[i]:2);
end;
end;
procedure find (n:integer; var a:vector);
{Найдёт самую длинную повторяющуюся комбинацию элементов в массиве a}
var i,j1,j,l,lmax,imax,jmax:integer;
m:array [0..size-1,0..size-1] of integer;
begin
{Заполнение матрицы}
for i:=1 to n{n-1} do begin writeln;
for j:=1{i+1} to n do begin
if a[i]=a[j] then m[i,j]:=1
else m[i,j]:=0;
write (m[i,j]:2);end;
end;
{Анализ диагоналей матрицы}
lmax:=0;
for j:=2 to n do begin
i:=1; j1:=j; l:=0;
while j1<=n do begin
if m[i,j1]=1 then begin
inc(l);
if l>lmax then begin
lmax:=l; imax:=i; jmax:=j1;
end;
end
else l:=0;
inc(i); inc(j1);
end;
end;
{Вывод результата}
writeln; i:=imax-lmax+1;
writeln ('imax=',imax,' jmax=',jmax,' lmax=',lmax,' i=',i);
for l:=1 to lmax do begin write (a[i]:2); inc (i); end;
end;
begin
fill(20,a);
find(20,a);
writeln (' Enter для выхода...');
reset (input); readln;
end.
К сожалению, это сработает не то, чтобы неправильно, но не так, как мы вправе ожидать. Например, на случайно сгенерированном тесте
4 4 4 5 4 5 4 5 3 4 4 3 3 3 5 2 5 3 3 3
результат будет
4 5 4 5
вместо 3 3 3. Почему так? Просто наш алгоритм не исключит пересекающиеся подстроки. Что именно происходит и какие единички
следовало бы убрать, покажем на рисунке (зачёркнутые зелёным единички - лишние):
Поскольку матрица симметрична, для выявления "пересекающихся" по столбцам цепочек не нужно строить её всю вместо половины,
достаточно манипуляции индексами начала и конца каждой цепочки. Это может потребовать многократного анализа матрицы M
программой, так что сложность алгоритма можно грубо оценить как N2*N/2
const size=50; {Возьмем размерность поменьше, для старых компиляторов}
type
vector= array [1..size] of integer;
matrix= array [1..size,1..size] of integer;
procedure find (n:integer; var a:vector);
{Найдёт самую длинную повторяющуюся комбинацию элементов в массиве a
Пытается исключить вложенные комбинации
}
var i,j,i1,j1,l,lmax,imin,jmin,imax,jmax:integer; cross:boolean;
m:array [0..size-1,0..size-1] of integer;
begin
{Заполнение матрицы}
for i:=1 to {n}n-1 do {begin writeln;}
for j:={1}i+1 to n do begin
if a[i]=a[j] then m[i,j]:=1
else m[i,j]:=0;
{write (m[i,j]:2);end;}
end; {writeln;}
{Анализ диагоналей матрицы - теперь многопроходный}
repeat
lmax:=0;
for j:=2 to n do begin
i:=1; j1:=j; l:=0;
while j1<=n do begin
if m[i,j1]=1 then begin
inc(l);
if l>lmax then begin
lmax:=l; imax:=i; jmax:=j1;
end;
end
else l:=0;
inc(i); inc(j1);
end;
end;
{Анализ и удаление "пересечений"}
cross:=false;
imin:=imax-lmax+1; jmin:=jmax-lmax+1;
writeln ('imin=',imin,' jmin=',jmin);
if jmin<=imax then begin
i1:=imin; cross:=true;
for j:=jmin to imax do begin
m[i1,j]:=0; inc(i1);
end;
end;
until cross=false;
{Вывод результата}
writeln; i:=imax-lmax+1;
writeln ('imax=',imax,' jmax=',jmax,' lmax=',lmax,' i=',i);
for l:=1 to lmax do begin write (a[i]:2); inc (i); end;
end;
var a:vector;
begin
a[1]:=4; a[2]:=4; a[3]:=4; a[4]:=5; a[5]:=4;
a[6]:=5; a[7]:=4; a[8]:=5; a[9]:=3; a[10]:=4;
a[11]:=4; a[12]:=3; a[13]:=3; a[14]:=3; a[15]:=5;
a[16]:=2; a[17]:=5; a[18]:=3; a[19]:=3; a[20]:=3;
find(20,a);
a[1]:=1; a[2]:=1; a[3]:=1; a[4]:=1; a[5]:=1; a[6]:=1;
find(6,a);
a[1]:=1; a[2]:=2; a[3]:=3; a[4]:=4; a[5]:=4; a[6]:=3;
a[7]:=2; a[8]:=1;
find(8,a);
writeln (' Enter для выхода...');
reset (input); readln;
end.
Эта версия прошла тесты вроде
1 1 1 1 1 1 1 1 1 1 2 1 2 1 2 1 2 1 2 1 2 1 2
а также безошибочно обработала те данные, для которых понадобилась мне, более детальных тестов я не делал, так что не гарантирую безошибочность подхода.
Если искомых цепочек несколько, будет найдена одна из них. В этом плане алгоритм нетрудно улучшить,
если при поиске максимальной длины цепочки заменить условие if l>lmax на if l>=lmax, а затем сделать ещё один проход,
который сохранит где-нибудь или напечатает все цепочки длиной l=lmax.
Разумеется, в реальном приложении и процедура find будет не печатать, а возвращать найденную подпоследовательность.
Лучшим решением было бы построить суффиксное дерево подстрок, но в реализации это намного сложнее.
 гостевая; E-mail
|