суффиксные деревья и поиск в строке

Вопросы написания собственного программного кода (на любых языках)

Модератор: Olej

Аватара пользователя
Olej
Писатель
Сообщения: 17564
Зарегистрирован: 24 сен 2011, 14:22
Откуда: Харьков
Контактная информация:

суффиксные деревья и поиск в строке

Непрочитанное сообщение Olej » 20 янв 2023, 20:00

Ещё инт ересная статья Суффиксное дерево на python
19 августа 2022 в 15:14
По поводу областей применения суффиксного дерева:
Применение суффиксного дерева

ST не только содержит все суффиксы, оно содержит все подстроки. И чтобы проверить, содержит ли text подстроку x, достаточно просто попробовать "прочитать" текст x, двигаясь от корня по рёбрам, и если это удаётся, то значит x является подстрокой.

С помощью суффиксного дерева можно за линейное время решать такие задачи:

Задача 1: Проверить, есть ли подстрока x в тексте text.

Задача 2: Найти наибольшую общую подстроку в текстах text1 и text2.

Задача 3: Найти самую длинную подстроку, которая встречается в тексте text более k раз.

Задача 4: Найти подстроку длины k, которая встречается максимальное количество раз.

Задача 5: Найдите в тексте топ 10 по частоте слов длины k или больше.

Задача 6: Найти в тексте text подстроку, которая подходит под регулярное выражение x, в котором есть один символ '*', соответствующий любой строке, в том числе пустой.

Задача 7: Дана база правильных слов. Напишите быструю функцию от аргумента word, исправляющую в слове word одну или две опечатки типа "одной буква заменена на другую", "удалена одна буква", "вставлена одна лишняя буква". Функция должна предлагать 10 вариантов для исправления опечаток, если входное слово word неправильное. Для того, чтобы функция работала быстро, можно и нужно построить некоторую структуру данных на базе правильных слов.

Задачи как бы простые, но сложность заключается в умении решать их за линейное время от размера входных данных.
Реализация на Python (python3):
pst.py
(3.3 КБ) 4 скачивания
Olej писал(а):
20 янв 2023, 17:14
Что примечательно, и что видно по картинке, что этот ресурс работает с русскоязычными входными текстами
Python в этом смысл интереснее (C & C++), по крайней мере для начала отработки, поскольку Python 3 использует по умолчанию кодировку UTF-8, поэтому с текстами на национальных языках будет работать изначально ... а в C & C++ - с этим придётся пободаться: переписать под wchar_t.

Аватара пользователя
Olej
Писатель
Сообщения: 17564
Зарегистрирован: 24 сен 2011, 14:22
Откуда: Харьков
Контактная информация:

суффиксные деревья и поиск в строке

Непрочитанное сообщение Olej » 20 янв 2023, 20:38

Olej писал(а):
20 янв 2023, 20:00
Реализация на Python (python3):
Ещё одна реализация на Python (python2 :!: ): Ukkonen's Suffix Tree Algorithm in Python Complete Version.
suffixtree.py
(9.46 КБ) 4 скачивания
Olej писал(а):
20 янв 2023, 20:00
Python в этом смысл интереснее (C & C++), по крайней мере для начала отработки, поскольку Python 3 использует по умолчанию кодировку UTF-8, поэтому с текстами на национальных языках будет работать изначально ... а в C & C++ - с этим придётся пободаться: переписать под wchar_t.
... или в Python 2 за счёт строки (2-й):

Код: Выделить всё

#!/usr/bin/env python2
# -*- coding: utf-8 -*-
...
Или просто переписать в Python 3 (из-за не актуальности уже Python 2), что обычно достаточно легко получается...

Ответить

Вернуться в «Программирование»

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и 2 гостя