Исследовательская группа

Лаборатория языковых инструментов

О применении методов решения задач semi-local lcs и semi-local sa к задаче поиска повторов в текстовых документах

March 16

В докладе будет рассмотрено применение строковых алгоритмов, широко применяемых для решения таких задач как LCS и SA ("поиске наибольшей общей подпоследовательности" и "выравнивании последовательностей"), к задаче поиска повторов в документации, а так же других текстовых документах. Рассматриваемые алгоритмы LCS и SA обеспечивают оптимальную асимптотику, но они позволяют решать лишь одну задачу, тогда как в [1] определяются задачи semi-local lcs и semi-local sa, являющиеся строгим надмножеством задач lcs и sa, которые могут быть решены за ту же асимптотику, но позволяют решать больше задач. Это становится возможным благодаря тесной связи теории кос, тропической алгебры, матриц Монжа. Эта связь и будет рассмотрена в докладе.


[1] https://arxiv.org/abs/0707.3619