Гость
Войти | Профиль | Очистить
Целевая тема:
Создать новую тему:
Автор:
Действия ...
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Поиск повторяющихся последовательностей / 20 сообщений из 20, страница 1 из 1
10.01.2013, 00:38
    #38104259
Homosum
Homosum
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск повторяющихся последовательностей
Здравствуйте, уважаемые форумчане.
Давно интересует тема поиска любых повторяющихся последовательностей внутри какого либо потока данных.

Вот например у нас есть строка в которой повторяются слова Hello, Fitness, World.

Код: c#
1.
F6HIW7CBCYFITNESSF@:NHelloH;;ITIHQ7CVJ6PWorldRP16YT03>:856FITNESSIMW?0AHelloL8OVGWorldAC;S;M3<O>4NFITNESSG8W>HelloDADHPX:5?KWorldH<:B



Любой человек эти слова там найдет. Причем повторяющиеся последовательности могут быть любыми. Слова даны чтобы было нагляднее.

А какие существуют алгоритмы нахождения повторяющихся последовательностей.
Может кто сталкивался или слышал?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
10.01.2013, 01:08
    #38104272
sphinx_mv
sphinx_mv
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск повторяющихся последовательностей
HomosumА какие существуют алгоритмы нахождения повторяющихся последовательностей.
Может кто сталкивался или слышал?Подобное используется в алгоритмах сжатия данных без потерь .
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
10.01.2013, 02:50
    #38104298
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск повторяющихся последовательностей
HomosumЛюбой человек эти слова там найдет. Причем повторяющиеся последовательности могут быть любыми. Слова даны чтобы было нагляднее.

Не знаю какие методы используют архиваторы. Но данная постановка немного отличается от архивации.

Я бы предложил для начала завернуть массив A в кольцо. И несколько раз поворачивать на 1 символ.
Получим множество колец {B}. При каждом повороте отмечать количество совпадений A и {Bi}.
в виде метрики {W}. В конце ранжируем кольца по метрикам и дальше - как фантазия подскажет.

Это так... типа мозговой штурм.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
10.01.2013, 09:20
    #38104397
Akina
Akina
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск повторяющихся последовательностей
http://algolist.manual.ru/search/lrs/index.php
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
10.01.2013, 10:07
    #38104449
sphinx_mv
sphinx_mv
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск повторяющихся последовательностей
maytonHomosumЛюбой человек эти слова там найдет. Причем повторяющиеся последовательности могут быть любыми. Слова даны чтобы было нагляднее.

Не знаю какие методы используют архиваторы. Но данная постановка немного отличается от архивации.Там тоже выполняют поисх в исходном тексте повторяющиеся последовательности бит/символов и заменяет их на более короткие в зависимост от частоты повторения найденой последовательности. В обощенном виде...
maytonЭто так... типа мозговой штурм.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
10.01.2013, 16:23
    #38105118
Homosum
Homosum
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск повторяющихся последовательностей
Спасибо всем кто откликнулся!
Но вот не совсем понятен подход некотрых алогримтов

например этого
Кодирование длин серий


Пример со строкой (пример на php)

Код: c#
1.
code = "fafaaaaaaaaaaaaa";



дает результат

Код: c#
1.
1f1a1f13a




Может для сжатия он и подходит, но меня интересует выделение повторяющихся последовательностей, а именно у нас есть ярковыраженная последовательность "fa".


Может сам алгоритм не совсем правильно подобран под задачу или это особенность всех алгоритмов сжатия данных?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
10.01.2013, 16:26
    #38105123
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск повторяющихся последовательностей
Homosum, исходя из тестового примера который ты привел тебе
run-length-encoding не нужен. Он тебе ничем не поможет.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
10.01.2013, 16:42
    #38105160
sphinx_mv
sphinx_mv
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск повторяющихся последовательностей
HomosumПример со строкой (пример на php)
Код: sql
1.
code = "fafaaaaaaaaaaaaa";

дает результат
Код: sql
1.
1f1a1f13a


Может для сжатия он и подходит, но меня интересует выделение повторяющихся последовательностей, а именно у нас есть ярковыраженная последовательность "fa".

Может сам алгоритм не совсем правильно подобран под задачу или это особенность всех алгоритмов сжатия данных?
Лемпель и Зив в помощь...
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
10.01.2013, 16:46
    #38105168
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск повторяющихся последовательностей
В задаче не хватает начальных условий. После поиска повторов Hello, Fitness, World оставшиеся
последовательности можно объявить цепочкой последовательностей из 1 символа и тоже
смерджить. Отсюда следующий вопрос. А почему вообще нельзя было смерджить по 1 букве
и объявить задачу решённой?

Должен быть какой-то лимит на минимальную длину последовательности.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
10.01.2013, 18:22
    #38105378
Homosum
Homosum
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск повторяющихся последовательностей
maytonВ задаче не хватает начальных условий. После поиска повторов Hello, Fitness, World оставшиеся
последовательности можно объявить цепочкой последовательностей из 1 символа и тоже
смерджить. Отсюда следующий вопрос. А почему вообще нельзя было смерджить по 1 букве
и объявить задачу решённой?

Должен быть какой-то лимит на минимальную длину последовательности.

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

В данном случае подразумевается, что последовательность состоит минимум из 2-х символов, но при этом в контексте одной последовательности отдается предпочтение более длинной.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
10.01.2013, 18:23
    #38105382
Homosum
Homosum
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск повторяющихся последовательностей
sphinx_mvHomosumПример со строкой (пример на php)
Код: sql
1.
code = "fafaaaaaaaaaaaaa";

дает результат
Код: sql
1.
1f1a1f13a


Может для сжатия он и подходит, но меня интересует выделение повторяющихся последовательностей, а именно у нас есть ярковыраженная последовательность "fa".

Может сам алгоритм не совсем правильно подобран под задачу или это особенность всех алгоритмов сжатия данных?
Лемпель и Зив в помощь...


Спасибо! Посмотрю!
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
10.01.2013, 20:22
    #38105535
BAZlST2
BAZlST2
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск повторяющихся последовательностей
Ахо-корасик - алгоритм
Регексп вообще курить
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
10.01.2013, 20:26
    #38105542
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск повторяющихся последовательностей
Да нет. Регексп ему тут не особо нужен. Тут с некоторой натяжкой
можно пожонглировать расстоянием Левинштейна. Если-бы это было
сравнение двух разных слов. Но здесь идёт тупое выкуривание
справочника из потока символов.

Кст. процесс поиска зависимостей внутри текста - дело увлекательное
и ... бесконечное (!). В хорошем тексте помимо шенноновских эффектов
есть еще и грамматика, морфология. Смысл. Стиль. Это всё можно
использовать в разработке архиваторов и авто-генерации словарей
как здесь.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
10.01.2013, 23:45
    #38105672
Homosum
Homosum
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск повторяющихся последовательностей
maytonДа нет. Регексп ему тут не особо нужен. Тут с некоторой натяжкой
можно пожонглировать расстоянием Левинштейна. Если-бы это было
сравнение двух разных слов. Но здесь идёт тупое выкуривание
справочника из потока символов.

Кст. процесс поиска зависимостей внутри текста - дело увлекательное
и ... бесконечное (!). В хорошем тексте помимо шенноновских эффектов
есть еще и грамматика, морфология. Смысл. Стиль. Это всё можно
использовать в разработке архиваторов и авто-генерации словарей
как здесь.

Супер! Сколько умных слов! Надо будет почитать.
Насчет выкуривания справочника из потока может быть это и есть самое емкое описание данной задачи.
Текст и слова даны для наглядности, а смысл извлекать последовательности из любого потока данных. Хотя анализ текста тоже очень интересует.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
11.01.2013, 00:39
    #38105708
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск повторяющихся последовательностей
Homosum, почитай здесь

http://compression.ru/?linksurl=

вот где ребята поднаторели в анализе текста.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
11.01.2013, 02:13
    #38105733
Програмёр
Програмёр
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск повторяющихся последовательностей
может я не прав, но разве тут не всё просто?
индексируем каждый символ/байт (далее предполагается что символ равен байту). Таким образом получаем до 255 массивов с номерами элементов в тексте. потом :
1. берём элемент из списка
2. плюсуем к его индексам 1 (просто запоминаем, индексы не меняем)
3. Ищем символ у которого сойдутся хотя бы 2 индекса с полученными.
4. Если нашли - идём на пункт 2. иначе считаем количество закончившихся на этом символе комбинаций. если больше одной - запоминаем позицию начала комбинации (точнее позиции)
5. получившиеся комбинации сортируем по длине по убыванию.
6. проходим по каждой и смотрим не является ли она частью предыдущих (лучше сравнивать по позациям, если начинается позже, а заканчивается раньше - значит часть). Отсеиваем все такие совпадения... и вроде как готово
7. думаем что делать с пересечениями комбинаций.

Если что не учёл, прошу не ругать сильно.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
11.01.2013, 11:39
    #38106070
Дмит
Дмит
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск повторяющихся последовательностей
автор"fafaaaaaaaaaaaaa";
а именно у нас есть ярковыраженная последовательность "fa".
хм, задача точно требует осмысления.
на мой взгляд, ярковыраженная последовательность "аa".
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
11.01.2013, 12:52
    #38106208
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск повторяющихся последовательностей
Дмитавтор"fafaaaaaaaaaaaaa";
а именно у нас есть ярковыраженная последовательность "fa".
хм, задача точно требует осмысления.
на мой взгляд, ярковыраженная последовательность "аa".
Там есть много чего ярко выраженного. В т.ч. нелинейная гистограмма появления
символов. И, развивая идею неограниченного словаря я могу напомнить
о существовании гипотетического архиватора который любое добавляемое
слово тут-же объявляет словарным. Такой архиватор даёт бешеный рост
архива на начальном этапе но на некой точке (не доходя до бесконечности)
внезапно обнаруживает неплохой profit в виде ratio.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
11.01.2013, 13:27
    #38106277
AndreTM
AndreTM
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск повторяющихся последовательностей
maytonмогу напомнить о существовании гипотетического архиватора который любое добавляемое слово тут-же объявляет словарным.Почему гипотетического?
В 1989-м я лично написал нечто подобное - надстройку на Форт-83, для хранения больших текстов. При этом особенности самого языка Форт таковы, что в нем это реализуется на раз-два, включая встроенные словари...
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
11.01.2013, 13:30
    #38106284
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск повторяющихся последовательностей
На каком-то сайте посвященном архиваторам
этот пример приводился как гипотетический.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Поиск повторяющихся последовательностей / 20 сообщений из 20, страница 1 из 1
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение  
Полит. конфиден.  
созд. / загр.: 489ms
Закрыть
start [/forum/topic.php?fid=16&mobile=1&tid=1341967]:
 0ms
get settings:
 11ms
get forum list:
 16ms
check forum access:
 4ms
check topic access:
 4ms
track hit:
 160ms
get topic data:
 10ms
get forum data:
 2ms
get page messages:
 43ms
get tp. blocked users:
 1ms
others: 238ms
total:  489ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]