2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 поиск максимально похожей подстроки
Сообщение06.11.2013, 15:45 
День добрый!

Задача такова: при данном тексте ($TEXT$) длины $n$ и данном образце ($SAMPLE$) длины $m$ найти позицию $i$, минимизирующую расстояние по Хэммингу между $SAMPLE$ и $TEXT[i : i + (m - 1)]$.

Причем сделано должно быть это либо сильно сокращенным перебором (сложность $\alpha n^2$, где $\alpha < \frac {1} {50}$), либо с линейно-логарифмической сложностью.

Особенность задачи - мощность алфавита $\left|S\right| << m$

Алгоритмы точного поиска не помогают, ибо перебирать все варианты $SAMPLE$ с ошибками очень долго.

Алгоритмы нечеткого поиска (те, что я смог найти) решают несколько другую задачу - они находят подстроки $TEXT$, расстояние по Хэммингу от которых до $SAMPLE$ не превосходит некоторой константы $K$. Мне это тоже не подходит, ибо при $K \approx L$ (а такое в моей задаче вполне реализуемо) их сложность вырождается до квадратичной.

Я в тупике. Подскажите, пожалуйста, какой алгоритм использовать мне следует.

 
 
 
 Re: поиск максимально похожей подстроки
Сообщение06.11.2013, 19:09 
Аватара пользователя
trympyrym
Алгоритмов море выбирайте, тот который вам больше подходит.

1) К примеру автомат сложность поиска будет $O(N)$, решение точное.
2) Через свёртку(корреляцию) в худшем случае $O(N*Log(N))$ в лучшем $O(N)$ решение использует другую метрику.
3) Случайным образом выбирать смещение образца, так что бы $\alpha < \frac {1} {50}$
4) Использовать отсечения на основе признаков. Признаки надо под конкретную задачу подбирать самому. Подход творческий.

 
 
 
 Re: поиск максимально похожей подстроки
Сообщение07.11.2013, 13:25 
Pavia в сообщении #785698 писал(а):
trympyrym
Алгоритмов море выбирайте, тот который вам больше подходит.


Да, действительно, есть море алгоритмов, в описании которых есть слова "строка" и "подстрока". В первом посте как раз описано, почему приведенные Вами подходы (кроме, разве что, 4-го) неприменимы к моей задаче. В любом случае спасибо за ответ

 
 
 [ Сообщений: 3 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group