Посоветуйте, как реализовать поиск в скользящем окне?

@CyberMyzhik · Регистрация: 23.06.2020

Студворк — интернет-сервис помощи студентам

Вообщем, проблема возникла, когда я столкнулся с алгоритмом сжатия LZ77. Принцип какой: мы имеем скользящее окно ( обычно оно 2, 4, 8, 16, 32 кб на выбор разработчика ) и буфер ( длиной обычно до 200 байт ). Надо найти в скользящем окне совпадающие строки с буфером ( т.е, Например, буфер = abcd, а скользящее окно = abvgggcd, то мне надо найти совпадающие строки ab и cd ).
Можете подсказать, как реализовать поиск в скользящем окне? Тупой перебор здесь категорически не подходит.

@Mikhaylo · 10.03.2022, 19:57

А вы побольше тестовых вариантов накидайте, чтобы понять, насколько однозначно вы выдвигаете техзадание.

буфер = abcd
окно1 = ssabc
окно2 = absabcssabcd

Что в этих примерах должно быть результатом поиска? А то на русском языке можно хоть что наформулировать, но суть не передать.

@Shamil1 · 11.03.2022, 10:05

Поиск подпоследовательности? Или, может быть, наибольшей общей подпоследовательности?

@CyberMyzhik · 11.03.2022, 10:22 **[ТС]**

Shamil1, Нет, надо найти не наибольшую общую подпоследовательность, а просто ранее встречающиеся части буффера, если так можно выразиться.
Mikhaylo, В случае с первым окном мы должны обнаружить ssabc, а со вторым окном мы должны обнаружить absabcssabcd ( выделил то, что мы должны найти, жирным курсивом )
В этом и заключается суть алгоритма: то, что встречалась ранее, мы должны найти.

@Shamil1 · 11.03.2022, 17:28

Сообщение от CyberMyzhik

буфер = abcd, а скользящее окно = abvgggcd

То есть, нужно найти подпоследовательность abcd в последовательности abvgggcd.

Тут только перебор. Сложность O(n).

Скользящее окно тут не особо поможет. Можно запоминать индекс вхождения первого символа и не искать, если он остаётся в окне.

@CyberMyzhik · 11.03.2022, 23:13 **[ТС]**

Shamil1, "То есть, нужно найти подпоследовательность abcd в последовательности abvgggcd."
Извините, но я не это имел в виду. Надо найти НЕ ТОЛЬКО ПОЛНОСТЬЮ, а и еще и ЧАСТИ ПОСЛЕДОВАТЕЛЬНОСТИ, т.е часть ab, часть cd, т.е то, что я описал немного выше. А насчёт окна... То скользящее окно и не должно помогать. Оно используется в алгоритме просто как место, где надо искать последовательность/части последовательности.

@Shamil1 · 12.03.2022, 00:05

CyberMyzhik,
Вы можете строго сформулировать, что нужно найти?

@Mikhaylo · 12.03.2022, 17:58

Еще примеры:
буфер abcd
окно1 = xaxbxcxd
окно2 = xdbcaxaaax

Добавлено через 1 минуту
Каждая буква буфера является частью подпоследовательности, значит можно выделить каждую букву, которая встречается в буфере, и ответ готов. Или же надо, чтобы было хотя бы две буквы подряд?

Новые блоги и статьи Все статьи Все блоги /
Уведомление о неверно выбранном значении справочника Maks 06.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "НарядПутевка", разработанного в конфигурации КА2. Задача: уведомлять пользователя, если в документе выбран неверный склад. . .	Установка Qt Creator для C и C++: ставим среду, CMake и MinGW без фреймворка Qt 8Observer8 05.04.2026 Среду разработки Qt Creator можно установить без фреймворка Qt. Есть отдельный репозиторий для этой среды: https:/ / github. com/ qt-creator/ qt-creator, где можно скачать установщик, на вкладке Releases:. . .	AkelPad-скрипты, структуры, и немного лирики.. testuser2 05.04.2026 Такая программа, как AkelPad существует уже давно, и также давно существуют скрипты под нее. Тем не менее, прога живет, периодически что-то не спеша дополняется, улучшается. Что меня в первую очередь. . .	Отображение реквизитов в документе по условию и контроль их заполнения Maks 04.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеСпецтехники", разработанного в конфигурации КА2. Данный документ берёт данные из другого нетипового документа. . .
Фото всей Земли с борта корабля Orion миссии Artemis II kumehtar 04.04.2026 Это первое подобное фото сделанное человеком за 50 лет. Снимок называют новым вариантом легендарной фотографии «The Blue Marble» 1972 года, сделанной с борта корабля «Аполлон-17». Новое фото. . .	Вывод диалогового окна перед закрытием, если документ не проведён Maks 04.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: реализовать программный контроль на предмет проведения документа. . .	Программный контроль заполнения реквизитов табличной части документа Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: 1. Реализовать контроль заполнения реквизита. . .	wmic не является внутренней или внешней командой Maks 02.04.2026 Решение: DISM / Online / Add-Capability / CapabilityName:WMIC~~~~ Отсюда: https:/ / winitpro. ru/ index. php/ 2025/ 02/ 14/ komanda-wmic-ne-naydena/

@CyberMyzhik 0 / 0 / 0 Регистрация: 23.06.2020 Сообщений: 166

	Посоветуйте, как реализовать поиск в скользящем окне? 10.03.2022, 17:08. Показов 889. Ответов 7 Метки нет (Все метки) Вообщем, проблема возникла, когда я столкнулся с алгоритмом сжатия LZ77. Принцип какой: мы имеем скользящее окно ( обычно оно 2, 4, 8, 16, 32 кб на выбор разработчика ) и буфер ( длиной обычно до 200 байт ). Надо найти в скользящем окне совпадающие строки с буфером ( т.е, Например, буфер = abcd, а скользящее окно = abvgggcd, то мне надо найти совпадающие строки ab и cd ). Можете подсказать, как реализовать поиск в скользящем окне? Тупой перебор здесь категорически не подходит. 0

@Mikhaylo 699 / 575 / 75 Регистрация: 20.09.2014 Сообщений: 3,730
	10.03.2022, 19:57
	А вы побольше тестовых вариантов накидайте, чтобы понять, насколько однозначно вы выдвигаете техзадание. буфер = abcd окно1 = ssabc окно2 = absabcssabcd Что в этих примерах должно быть результатом поиска? А то на русском языке можно хоть что наформулировать, но суть не передать. 1

@Shamil1 Модератор 3136 / 2283 / 469 Регистрация: 26.03.2015 Сообщений: 8,886
	11.03.2022, 10:05
	Поиск подпоследовательности? Или, может быть, наибольшей общей подпоследовательности? 1

@CyberMyzhik 0 / 0 / 0 Регистрация: 23.06.2020 Сообщений: 166
	11.03.2022, 10:22 [ТС]
	Shamil1, Нет, надо найти не наибольшую общую подпоследовательность, а просто ранее встречающиеся части буффера, если так можно выразиться. Mikhaylo, В случае с первым окном мы должны обнаружить ssabc, а со вторым окном мы должны обнаружить absabcssabcd ( выделил то, что мы должны найти, жирным курсивом ) В этом и заключается суть алгоритма: то, что встречалась ранее, мы должны найти. 0

@CyberMyzhik 0 / 0 / 0 Регистрация: 23.06.2020 Сообщений: 166
	11.03.2022, 23:13 [ТС]
	Shamil1, "То есть, нужно найти подпоследовательность abcd в последовательности abvgggcd." Извините, но я не это имел в виду. Надо найти НЕ ТОЛЬКО ПОЛНОСТЬЮ, а и еще и ЧАСТИ ПОСЛЕДОВАТЕЛЬНОСТИ, т.е часть ab, часть cd, т.е то, что я описал немного выше. А насчёт окна... То скользящее окно и не должно помогать. Оно используется в алгоритме просто как место, где надо искать последовательность/части последовательности. 0

@Shamil1 Модератор 3136 / 2283 / 469 Регистрация: 26.03.2015 Сообщений: 8,886
	12.03.2022, 00:05
	CyberMyzhik, Вы можете строго сформулировать, что нужно найти? 0

@Mikhaylo 699 / 575 / 75 Регистрация: 20.09.2014 Сообщений: 3,730
	12.03.2022, 17:58
	Еще примеры: буфер abcd окно1 = xaxbxcxd окно2 = xdbcaxaaax Добавлено через 1 минуту Каждая буква буфера является частью подпоследовательности, значит можно выделить каждую букву, которая встречается в буфере, и ответ готов. Или же надо, чтобы было хотя бы две буквы подряд? 0