|
|
|
найти паттерны в тексте
|
|||
|---|---|---|---|
|
#18+
добрый день, имеется 60 M фрагментов текста общим объёмом 720 GB, они хранятся в неком хранилище данных. постоянно добавлются новые. задача: необходимо уменьшить занимаемое место любым способом, без потери информации. я пробовал различные варианты компрессии, удается уменьшить в 3-4 раза, что не достаточно. найден такой путь: многие фрагменты текста похожи, например: строка 1: "Повышение артериального давления 145/93. Врожденное сужение или атеросклероз аорты." строка 2: "Повышение артериального давления 146/94. Врожденное сужение или атеросклероз аорты." можно в хранить только изменяющееся значение {145/93} , а основной текст записать отдельно: pattern: "Повышение артериального давления {0}/{1}. Врожденное сужение или атеросклероз аорты." этот подход уменьшает объём данных в 50-60 раз, то что надо. НО: как найти все паттерны? в ручную нереально, их несколько тысяч разновидностей. были бы это xml, я бы получил xsd всех строк и их бы сравнивал. или JSON, можно получить схему и их сравнить. но к сожалению формат не определён. какие варианты, в какую сторону копать? спасибо. извиняюсь за кросс ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 22.11.2016, 15:41 |
|
||
|
найти паттерны в тексте
|
|||
|---|---|---|---|
|
#18+
Покопай в сторону устройства архиваторов, они за счет построения словаря сжимают. Получится примерно так Слово 50: "Повышение артериального давления" Слово 51: "Врожденное сужение или атеросклероз аорты." строка 1: "{50} 145/93. {51}" строка 1: "{50} 145/94. {51}" ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 22.11.2016, 15:54 |
|
||
|
найти паттерны в тексте
|
|||
|---|---|---|---|
|
#18+
valv, Физически это что? Много мелких файлов? Один гигантский файл? Дальше что должно с этим происходить? Просто лежать-храниться? Если много мелких файлов и нужно просто хранить, то есть архиваторы, которые умеют составлять общий словарь для пачки файлов, например, WinRAR (у него это называется solid-архив). Если файлы однообразные, то разница по сравнению с обычными архивами очень заметная. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 22.11.2016, 17:25 |
|
||
|
найти паттерны в тексте
|
|||
|---|---|---|---|
|
#18+
miksoftvalv, Физически это что? Много мелких файлов? Один гигантский файл? Дальше что должно с этим происходить? Просто лежать-храниться? Если много мелких файлов и нужно просто хранить, то есть архиваторы, которые умеют составлять общий словарь для пачки файлов, например, WinRAR (у него это называется solid-архив). Если файлы однообразные, то разница по сравнению с обычными архивами очень заметная. это типа массив string[]. из него переодически читают отдельные строки. если хранить в массиве фрагменты текста "как есть", они занимают 720, GB что неприемлимо. а если хранить только изменяемые значения + указатель на паттерн, то примерно 10-20 GB, это можно. вопрос в том, как найти все паттерны. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 22.11.2016, 18:52 |
|
||
|
найти паттерны в тексте
|
|||
|---|---|---|---|
|
#18+
valv, Тебе стоит рассмотреть все дополнительные свединя о данных о которых ты умолчал. Возможно там найдёшь более простое решение. Почему более простое: если рассматривать задачу в таком виде как ты описал, то решение очень не простое и требует определённый уровень подготовки. Если ты студент (я не хочу тебя обидеть, просто реально оцени свои возможности) то тебе это не по зубам. Если ты готов провозится с задачей несколько месяцев, предлагаю сделать вместе. Мне тоже пригодится но не сильно нужно. Вопервых это задача кластеризации. Оптимальное решение только полный перебор. Во вторых эвристическое решение требует уже огромных вычислительных ресурсов. Решение: По каждой строке нужно построить суффиксное дерево. Рабочий набор кластеров/паттернов это набор суффиксных деревев. Итеративный эвристический вариан построения кластера: Сравниваем два дерева и вычисляем коэффициент схожести. (Удаление о ценра кластера) При необходимости меняем паттерн кластера. Построить деревья уже сложная вычислительная задача. Линейный поиск по списку елементов кластера тоже не быстрый. Наверняка придётся соединять деревья - плюс к сложности. Иои строить индекс по деревьям - двойной плюс к сложности. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 22.11.2016, 19:38 |
|
||
|
найти паттерны в тексте
|
|||
|---|---|---|---|
|
#18+
mikron, спасибо большое, сдвинулся с мёртвой точки. прочитал про суффиксное дерево, похоже, то что надо. на данный момент реализовал такой примерно алгоритм: строю суффикные массивы для для 3 фрагментов. сравниваю 3 массива: если (совпадающие строки одинаковы во всех трёх массивах) & (количество совпадающих строк) > (количество разных)*K), нахожу самую длинную несовпадающую строку и на основании этого строю regular expression. типа такого: Код: sql 1. дальше элементарно: все фрагменты текста, совпадающие с шаблоном regular expression, уходят из рассмотрения. для части массива удалось найти паттерны. но реализация имеет проблемы, и корень проблемы в неправильном сравнении. тут я увяз... нашлось несколько реализаций сравнения, вот такой алгоритм например: comparison of two suffix tree-based document clustering algorithms . но это не то. ты пишешь: mikronвычисляем коэффициент схожести. (Удаление о ценра кластера) При необходимости меняем паттерн кластера вот это вот кажется важно для алгоритма. но не могу найти информацию. по каким ключевым словам искать? "cluster pattern"? "suffix tree"? ссылку бы на книгу или статью, объясняющую... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 23.11.2016, 19:57 |
|
||
|
найти паттерны в тексте
|
|||
|---|---|---|---|
|
#18+
valv, как мера схожести текстов часто используют кол-во операций редактирования что бы получить из текста1 текст2. Для твоего случая может выглядеть так: перестановка фрагментов текста 1, удаление частей текста 0, добавление текста log2(длина вставки). Функция схожести строится из задачи кластеризации. Единого стандарта нет и быть не может. Читай про методы кластеризации. У тебя текста много. Bottomup подход потребует для начала построит все суффиксы деревья. Самое экономичное представление (надо проверить) х8. 5ТБ данных. потом сравнение. каждого с каждым. можно ускорить если сначала соеденить деревья. (minimum O(N x log(N)) ) При удачном выборе метрики можно быстро найти наименьшую дистанцию. Но на следующем шаге придётся заново соединят деревья. TopDown выглядит реалистичней. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 23.11.2016, 22:12 |
|
||
|
найти паттерны в тексте
|
|||
|---|---|---|---|
|
#18+
valvдобрый день, имеется 60 M фрагментов текста общим объёмом 720 GB, они хранятся в неком хранилище данных. постоянно добавлются новые. задача: необходимо уменьшить занимаемое место любым способом, без потери информации. я пробовал различные варианты компрессии, удается уменьшить в 3-4 раза, что не достаточно. найден такой путь: многие фрагменты текста похожи, например: строка 1: "Повышение артериального давления 145/93. Врожденное сужение или атеросклероз аорты." строка 2: "Повышение артериального давления 146/94. Врожденное сужение или атеросклероз аорты." можно в хранить только изменяющееся значение {145/93} , а основной текст записать отдельно: pattern: "Повышение артериального давления {0}/{1}. Врожденное сужение или атеросклероз аорты." этот подход уменьшает объём данных в 50-60 раз, то что надо. НО: как найти все паттерны? в ручную нереально, их несколько тысяч разновидностей. были бы это xml, я бы получил xsd всех строк и их бы сравнивал. или JSON, можно получить схему и их сравнить. но к сожалению формат не определён. какие варианты, в какую сторону копать? спасибо. извиняюсь за кросс а ты думаешь стандартные алгоритмы сжатия это не делают? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.11.2016, 15:32 |
|
||
|
найти паттерны в тексте
|
|||
|---|---|---|---|
|
#18+
valv, определённо тебе нужен архиватор. Сильно сомневаюсь что мы кустарными методами сможем выровнять твой "медицинский поток сознания" хотя-бы до тех объемов которые выдал архиватор. Кстати какой ты юзал? В большинстве из них захардкоден лимит на размер и разрядность справочника. Скорее всего rar и zip с дефолтными настройками тебе не подойдут. Левенштейн для поиска подобий тебе вобщем-то подходит но он работает долго и тебе надо сравнивать все со всеми. Тоесть - возведи в квадрат объем обработки + сам дядька Левин кушает матрицу сравнений для двух строк с точки зрения количества внутренних операций. +Если у тебя уж совсем уйма времени и хоца ковырять текст - то почитай про N-граммный анализ. Я думаю он поможет искать похожие фразочки. https://habrahabr.ru/post/114997/ По сути тебе нужен эффективный нечеткий индекс по этим 720 Gb. Хотя я ума ни приложу что ты с ними будешь дальше делать? Создавать свой дезархиватор? А будет-ли он эффективен? Врачи и больные не будут ждать пока ты колбасишь кило-тонны Strings и делаешь replacements. А нагрузка на heap? Текстовые замены - это одни из самых коварных операций. При кажущейся простоте - под капотом колоссальная работа. Ну и самый главный вопрос. А почему-бы не положить это всё в БД? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.11.2016, 23:29 |
|
||
|
|
start [/forum/topic.php?fid=16&fpage=25&tid=1340559]: |
0ms |
get settings: |
9ms |
get forum list: |
18ms |
check forum access: |
4ms |
check topic access: |
4ms |
track hit: |
54ms |
get topic data: |
8ms |
get forum data: |
2ms |
get page messages: |
40ms |
get tp. blocked users: |
1ms |
| others: | 225ms |
| total: | 365ms |
| 0 / 0 |
