1. Допустим, текст отредактировали, но кусок с цитатой не изменился. Надо выделить цитату из текста. Под этим понимается, указать местоположение цитаты.
В большинстве случаев здесь достаточно поиска подстроки в строке. Но иногда текст могут так отредактировать, что в него добавится ещё один фрагмент с таким же текстом. Тогда следует проанализировать окружающий цитату текст (контекст), и выбрать тот фрагмент, у которого контекст больше похож на контекст первоначальной цитаты.
2. Допустим, текст отредактировали, несильно поменялась и цитата (заменили пару слов, исправили несколько ошибок). Надо выделить цитату из текста.
Здесь почти аналогично предыдущему случаю, но вместо поиска подстроки в строке прийдётся применять приближённый поиск.
3. Допустим, текст отредактировали так, что, похоже, в нём уже нет того фрагмента. Надо сказать "не могу найти цитату".
Здесь аналогично предыдущему случаю, за исключением того, что нужно указать некоторый порог, после которого фрагменты считаются непохожими.
Задача:
Разработать структуру данных, представляющую собой "ссылку на цитату" — то, что подаётся на вход алгоритма.
Разработать алгоритм, который будет по ссылке на цитату выделять, возможно изменившуюся, цитату из текста, или говорить, что цитаты в тексте уже нет.
Пример реализации:
В качестве структуры данных взять пару (весь исходный текст, цитата) (или (весь исходный текст, смещение начала цитаты, длина цитаты)).
Для приближённого поиска подстроки в строке: перебрать все смещения от начала текста, и сравнить с помощью метрики Левенштейна исходную цитату и фрагмент той же длины, смещённый от начала текста. Выбрать argmin метрики. Но если есть несколько несильно отличающихся фрагментов-кандидатов, с близкими значениями метрики, расширить цитату с обеих сторон на несколько слов, добавив "контекст", повторить поиск для "расширенной цитаты". Если min метрики слишком большой, ответить, что цитату невозможно найти.
Дополнительно: размер текста — как сообщение в форуме (несколько килобайт, но иногда до 64K). Алгоритм должен вызываться, например, каждый раз при редактировании сообщения — то есть, работать за время меньше секунды.
Вопросы:
Как бы вы решили эту задачу?
Как можно уменьшить размер "ссылки на цитату"? (приходит в голову вместо всего исходного текста брать только "расширенную цитату")
Как можно ускорить алгоритм (возможно, с потерей точности — здесь точность не особо важна, как видите, задача не особо формализована)
Может ли такой алгоритм, в принципе, применяться на практике, при заданных ограничениях (не слишком ли он сложный)?
PS. По моему, похожая задача решается в системах контроля версий. Главное отличие моей задачи в том, что может поменяться одновременно и фрагмент и окружающий текст.
