Xpoint
   [напомнить пароль]

Алгоритм поиска совпадающих групп

Метки: [без меток]
2008-01-11 10:32:36 [обр] Андрей Пахомов(0/310)[досье]

День добрый.

Имеется следующая задача:

есть две группы элементов, допустим чисел (хотя это не важно, в данном случае это просто пример ):

позиция0123456789101112
группа 112345247845
группа 21012311524781245

Надо выделить цепочки из одинаковых последовательностей элементов и их позиции. Поскольку в группах некоторые элементы могут встречаться несколько раз, поэтому стоит задача нахождения именно цепочек максимальной длины.
То есть в приведенном примере:

цепочкапозиция
группа 1группа 2
1,2,301
5,2,4,7,845
4,5911

Поскольку элементов может быть очень много (несколько сотен или несколько тысяч), строить массивы из позиций последовательностей одного, двух, трех и т.д. элементов в обоих группах и последующего их анализа пересечений индексов (это пока единственное что пришло мне в голову) не хочется, ибо это будет долго и ресурсоемко. Есть ли способы более простые ?

спустя 12 минут [обр] Lynn «Кофеман»(0/571)[досье]

А почему у третьей цепочки начало в первой группе в позиции 9, а не 3? Т.е. как должны обрабатываться случаи когда цепочка встречается несколько раз?

Пока, то что вы описали очень напоминает diff «наоборот».

$ diff -y a b
      > 10
1       1
2       2
3       3
4     | 11
5       5
2       2
4       4
7       7
8       8
      > 12
4       4
5       5
спустя 39 минут [обр] Андрей Пахомов(0/310)[досье]

Да, результат diff-а очень похож на то, что нужно получить.

А почему у третьей цепочки начало в первой группе в позиции 9, а не 3?

потому что 4,5 в первой группе на позиции 3 пересекается с цепочкой 5,2,4,7,8 на позиции 4. То есть мне надо чтобы сначала формировались самые длинные цепочки, потом более короткие и т.д. до цепочки из одного элемента, при этом пересечения цепочек происходить не должно. Понятное дело, что количество цепочек должно совпадать в обеих группах, то есть случая когда мы для одной цепочки из группы 1 пишем 2 индекса из группы 2 быть не может.

спустя 8 минут [обр] Андрей Пахомов(0/310)[досье]

Все, фраза diff натолкнула меня на мысль что искать, и выяснилось, что, то что мне нужно называется:
Наибольшая общая подпоследовательность

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

Powered by POEM™ Engine Copyright © 2002-2005