ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Поиск повторяющихся последовательностей
20 сообщений из 20, страница 1 из 1
Поиск повторяющихся последовательностей
    #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, 00:38
| Ответить | Цитировать | Написать  
Поиск повторяющихся последовательностей
    #38104272
sphinx_mv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
sphinx_mv
Участник
HomosumА какие существуют алгоритмы нахождения повторяющихся последовательностей.
Может кто сталкивался или слышал?Подобное используется в алгоритмах сжатия данных без потерь .
...
Рейтинг: 0 / 0
10.01.2013, 01:08
| Ответить | Цитировать | Написать  
Поиск повторяющихся последовательностей
    #38104298
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
HomosumЛюбой человек эти слова там найдет. Причем повторяющиеся последовательности могут быть любыми. Слова даны чтобы было нагляднее.

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

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

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

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

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


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

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



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

Код: c#
1.
1f1a1f13a




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


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

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


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

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

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

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

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

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

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


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

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


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

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

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

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

http://compression.ru/?linksurl=

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

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


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