Привет,

Нужны советы по решению одной извращенной задачи.

Есть два CSV файла например:

a,d
b,e
c,f

и

a b c,d e f

Это две таблички одна состоит из трех строк каждая с 2мя колонками, вторая одна строка 2 колонки.
Надо сравнить таблицы и получить общую последовательность. Используя стандартный алгоритм LCS получаем:

a,d b,e c,f
a b c,d e f

LCS:

a,b,e f

Хотя если расматривать как таблички:

a,d
b,e
c,f

и

a d
b e
c, f

то строки получаются равные, 3 строки объеденные в одну. Но не понятно как преобразовать строки, в каждом документе кол. колонок разное. Бьюсь 3 неделю, помогите с алгоритмом.

Не пойму задачу. Проблема запятые убрать, что ли?
И что такое "стандартный алгоритм LCS"? 

Earnest,

Сорри, буду писать немного подробней. LCS (Наибольшая общая подпоследовательность), использовал стандартный метод динамического программирования. Проблема состоит в следующем: нужен правильный алгоритм "устранения запятых", для получения правильной последовательности данных, или поиска общей подпоследовательности в данных, которые имеют структуру.

Например данные

a,с
b,d

и

a b, c d 

Если представить как две строки получаем:
a,с b,d
a b, c d 

Буквы с b меняются местами. Другой пример:

a,с b
b,d

и

a b, c d 

a,с b b,d
a b, c d 

Общая подпоследовательность
a,b d

Хотя она должна включать все символы кроме второй b.

Просто данные имеют структуру таблицы, более нормальное представление:

a | с 
   | b
------
b | d

и

a  | c
b  | d 

Таким образом символы читаются в последовательности: колонка, следующая колонка, следующая строка и т. д 
Получается а, с b, b, d
и a b, c d

И тут сама задача или модифицировать матрицу ДП, с учётом разбиения колонок на строки, или как то читать данные.



Это сообщение отредактировал(а) aggressorus - 10.12.2008, 19:24

Сломал мозг.
Дай пожалуйста четкий критерий "правильности" устранения запятых. Потом будем решать задачу.

SoWa, 

разбить/объединить колонки/строки, для получения максимально общей подстроки.

Тот же пример:

a | с 
   | b
------
b | d

и

a  | c
b  | d 

Если разбить колонки на строки:
a  | c
-------
b  | d

Получим общую последовательность a, c, b, d.  

Я сам сломал мозг пока думал критерии. Сказали вот данные покажи нам разницу!

Добавлено через 5 минут и 49 секунд
Просто проблема в том что визуально разницы между данными нету, а вот при чтении получается есть.

Так. Худо бедно стало понятнее, но все-же, возможно предложу нужное, а мб не то
Смотри. Любая таблица состоит из строк(даж единичной длинны), поставленых в колонки.
Самое простое- выставлять в одну строку все строчки таблицы.

Кстати, если можешь- нарисуй таблицы на бумажке, отскань и выложи  Так будет проще понять тебя

, Мы тут все тупые  и ленивые  тормоза.... Пожалуйста! Нужны полные определения, кто, какие...  Определения, блин!!!. Желательно со ссылками... Правильные запятые, правильные подпоследовательности, ... зона, блин... без правильного правила залетишь неподеццки...

SoWa, 
Спасибо, завтра выложу всё что имею по теме 

Добавлено через 51 секунду
ksnk, 
Уже понял, исправлюсь. 

ksnk, ты суров  какая, собственно, разница, каким он будет методом сравнивать? Поставлена задача преобразовать таблицы до такого вида, чтобы к ним можно было применить данный алгоритм. Очевидно, что он используется для строк. Ищем метод приведения таблиц к строкам ^_^

Привет,

Вот накидал тестовые данные, в приложении pdf файл.

Сcылки:

LCS ( Longest Common Subsequence)

LCS 1
LCS 2

Edit Script 
 An O(ND) Difference Algorithm and Its Variations 



Присоединённый файл ( Кол-во скачиваний: 8 )
 task.pdf 46,92 Kb

Хм... Извиняюсь! Ну, за всех, конечно, не скажу, однако за себя - так и есть!   

Ладно, проехали  Вон нам выложили данные.

Смотри, что мне думается.
Пустые зоны все в пределах одного столбца убиваем обьединением в одну ячейку.
Допустим было

станет

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

С этим понятно. 



Тут немного не понял, не могли бы вы уточнить. С первыми 2мя столбцами должно сработать. А вот со столбцами Склад и Магазин, не сработает. Они должны быть объедены слева направо. Тогда всё получиться. Вот как определить, что с чем объединять? Были у меня две идеи как сравнить без преобразования таблиц.
1) Можно применить "жадные алгоритм". 



Так вроде будет работать стабильно, но оптимальность решения всегда будет под сомнением. 

Пробовал использовать алгоритм LIS (Longest Increasing Subsecuence)

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

 

Уф, уже сплю и плохо соображаю о твоих постах )
Что касается столбиков, где надо обьединять по горизонтали.
Ерунда. Просто включи в вышенаписаный мной метод такое уточнение- длинну ячейки.
Т.е. таблица 1 была

А вторая:

Итак получим, что обе ячейки будут "отображаться" в одну длинную.
черт, мб непонятно, да и сам слов подобрать не могу, но попробуй осилить: обе ячейки при поиске будут сравниваться с этой длинной ячейкой.

Осилил  Просто размера колонки нету, это просто "," в данных. Буду думать как это закодить.