Смотри. Любая таблица состоит из строк(даж единичной длинны), поставленых в колонки.
Самое простое- выставлять в одну строку все строчки таблицы.
Кстати, если можешь- нарисуй таблицы на бумажке, отскань и выложи
Так будет проще понять тебя| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Сравнение структурированных данных |
| Автор: aggressorus 10.12.2008, 16:45 |
| Привет, Нужны советы по решению одной извращенной задачи. Есть два 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 неделю, помогите с алгоритмом. |
| Автор: Earnest 10.12.2008, 19:06 |
| Не пойму задачу. Проблема запятые убрать, что ли? И что такое "стандартный алгоритм LCS"? |
| Автор: aggressorus 10.12.2008, 19:20 |
| 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 И тут сама задача или модифицировать матрицу ДП, с учётом разбиения колонок на строки, или как то читать данные. |
| Автор: SoWa 10.12.2008, 19:45 |
| Сломал мозг. Дай пожалуйста четкий критерий "правильности" устранения запятых. Потом будем решать задачу. |
| Автор: aggressorus 10.12.2008, 19:54 |
| SoWa, разбить/объединить колонки/строки, для получения максимально общей подстроки. Тот же пример: a | с | b ------ b | d и a | c b | d Если разбить колонки на строки: a | c ------- b | d Получим общую последовательность a, c, b, d. Я сам сломал мозг пока думал критерии. Сказали вот данные покажи нам разницу! Добавлено через 5 минут и 49 секунд Просто проблема в том что визуально разницы между данными нету, а вот при чтении получается есть. |
| Автор: SoWa 10.12.2008, 21:21 |
| Так. Худо бедно стало понятнее, но все-же, возможно предложу нужное, а мб не то Смотри. Любая таблица состоит из строк(даж единичной длинны), поставленых в колонки. Самое простое- выставлять в одну строку все строчки таблицы. Кстати, если можешь- нарисуй таблицы на бумажке, отскань и выложи Так будет проще понять тебя |
| Автор: ksnk 10.12.2008, 21:27 | ||
|
| Автор: aggressorus 10.12.2008, 21:27 |
| SoWa, Спасибо, завтра выложу всё что имею по теме Добавлено через 51 секунду ksnk, Уже понял, исправлюсь. |
| Автор: SoWa 10.12.2008, 22:21 | ||||
ksnk, ты суров какая, собственно, разница, каким он будет методом сравнивать? Поставлена задача преобразовать таблицы до такого вида, чтобы к ним можно было применить данный алгоритм. Очевидно, что он используется для строк. Ищем метод приведения таблиц к строкам ^_^ |
| Автор: aggressorus 11.12.2008, 14:50 |
| Привет, Вот накидал тестовые данные, в приложении pdf файл. Сcылки: LCS ( Longest Common Subsequence) http://algolist.manual.ru/search/lcs/simple_lcs.php http://ocw.mit.edu/NR/rdonlyres/Electrical-Engineering-and-Computer-Science/6-046JFall-2005/6939E270-F2FA-4C0E-921C-BBA7886B9573/0/lec15.pdf Edit Script http://www.xmailserver.org/diff2.pdf |
| Автор: ksnk 11.12.2008, 15:23 | ||
Хм... Извиняюсь! Ну, за всех, конечно, не скажу, однако за себя - так и есть!  |
| Автор: SoWa 11.12.2008, 16:25 | ||||
| Ладно, проехали Вон нам выложили данные. Смотри, что мне думается. Пустые зоны все в пределах одного столбца убиваем обьединением в одну ячейку. Допустим было
станет
Далее, все ячейки в обоих таблицах сдвигаем вверх, но при этом где-то запоминаем их настоящие координаты. Далее простым сравнением попарно определяем общие данные. По рисункам вроде должно работать |
| Автор: aggressorus 11.12.2008, 16:56 | ||||||
С этим понятно.
Тут немного не понял, не могли бы вы уточнить. С первыми 2мя столбцами должно сработать. А вот со столбцами Склад и Магазин, не сработает. Они должны быть объедены слева направо. Тогда всё получиться. Вот как определить, что с чем объединять? Были у меня две идеи как сравнить без преобразования таблиц. 1) Можно применить "жадные алгоритм".
Так вроде будет работать стабильно, но оптимальность решения всегда будет под сомнением. Пробовал использовать алгоритм LIS (http://www.algorithmist.com/index.php/Longest_Increasing_Subsequence) Для каждого слова делаем список позиций, на которых это слово встречается в другой таблице. Применяем алгоритм LIS получаем наибольшую возрастающую последовательность, которая идентична наибольшей общей последовательности. Но я застрял с определением критериев больше, меньше для каждой позиции. |
| Автор: SoWa 11.12.2008, 17:06 | ||||
| Уф, уже сплю и плохо соображаю о твоих постах ) Что касается столбиков, где надо обьединять по горизонтали. Ерунда. Просто включи в вышенаписаный мной метод такое уточнение- длинну ячейки. Т.е. таблица 1 была
А вторая:
Итак получим, что обе ячейки будут "отображаться" в одну длинную. черт, мб непонятно, да и сам слов подобрать не могу, но попробуй осилить: обе ячейки при поиске будут сравниваться с этой длинной ячейкой. |
| Автор: aggressorus 11.12.2008, 17:17 | ||
Осилил Просто размера колонки нету, это просто "," в данных. Буду думать как это закодить. |
| Автор: SoWa 11.12.2008, 19:31 |
| У меня по этому поводу созрела мысля. Но только пока не понимаю, как именно будет таблица приводиться в исходных данных. Если не сложно- таблицы из твоего примера еще приведи в виде строчек через запятую. И подумаем дальше |
| Автор: aggressorus 11.12.2008, 19:37 | ||||
Вот что получилось. |
| Автор: SoWa 11.12.2008, 20:26 |
| В общих случаях. В первой таблице все, думаю ясно. А вот со второй, да. Смотри. Строки, содержащие два и более элемента будем считать "основными". Если далее опознаем строку, или несколько, состоящих из 1 элемента- то значит они находятся в "высокой" ячейке, заголовок которой- последнее слово предыдущей строки. По крайней мере с таким описанием уже можно что-то делать. Если что-то не понятно, спрашивай. Постараюсь конкретизировать. |
| Автор: aggressorus 12.12.2008, 16:35 | ||
| SoWa, Огромно спасибо за идею. Я принцип понял. Надо собрать рядки по строкам и потом "вытолкнуть" последовательно каждый рядок. Например:
Объединяем ячейки A c C, потом B c D. И получаем правильную строку A C B D. Буду кодить посмотрим, должно сработать. |
| Автор: SoWa 12.12.2008, 21:20 |
| Мм, одно дополнение "под пол-литра водки" В зависимости от предыдущей "длинной" последовательности выбирай, что следует обьединять- ячейки в строках или столбцах. Но это уже оффтоп Рад, что смог помочь тебе! |
| Автор: aggressorus 30.12.2008, 13:15 |
Ух, сделал! Все работает, есть мелкие ошибки, но они не существенны  SoWa, Спасибо за помощь. Поздравляю всех с наступающим НГ. |
