Есть текст, есть цитата из него.

Примеры того, что надо уметь:

1. Допустим, текст отредактировали, но кусок с цитатой не изменился. Надо выделить цитату из текста. Под этим понимается, указать местоположение цитаты.
В большинстве случаев здесь достаточно поиска подстроки в строке. Но иногда текст могут так отредактировать, что в него добавится ещё один фрагмент с таким же текстом. Тогда следует проанализировать окружающий цитату текст (контекст), и выбрать тот фрагмент, у которого контекст больше похож на контекст первоначальной цитаты.

2. Допустим, текст отредактировали, несильно поменялась и цитата (заменили пару слов, исправили несколько ошибок). Надо выделить цитату из текста.
Здесь почти аналогично предыдущему случаю, но вместо поиска подстроки в строке прийдётся применять приближённый поиск.

3. Допустим, текст отредактировали так, что, похоже, в нём уже нет того фрагмента. Надо сказать "не могу найти цитату".
Здесь аналогично предыдущему случаю, за исключением того, что нужно указать некоторый порог, после которого фрагменты считаются непохожими.

Задача:
Разработать структуру данных, представляющую собой "ссылку на цитату" — то, что подаётся на вход алгоритма.
Разработать алгоритм, который будет по ссылке на цитату выделять, возможно изменившуюся, цитату из текста, или говорить, что цитаты в тексте уже нет.

Пример реализации:
В качестве структуры данных взять пару (весь исходный текст, цитата) (или (весь исходный текст, смещение начала цитаты, длина цитаты)).
Для приближённого поиска подстроки в строке: перебрать все смещения от начала текста, и сравнить с помощью метрики Левенштейна исходную цитату и фрагмент той же длины, смещённый от начала текста. Выбрать argmin метрики. Но если есть несколько несильно отличающихся фрагментов-кандидатов, с близкими значениями метрики, расширить цитату с обеих сторон на несколько слов, добавив "контекст", повторить поиск для "расширенной цитаты". Если min метрики слишком большой, ответить, что цитату невозможно найти.

Дополнительно: размер текста — как сообщение в форуме (несколько килобайт, но иногда до 64K). Алгоритм должен вызываться, например, каждый раз при редактировании сообщения — то есть, работать за время меньше секунды.

Вопросы:
Как бы вы решили эту задачу?
Как можно уменьшить размер "ссылки на цитату"? (приходит в голову вместо всего исходного текста брать только "расширенную цитату")
Как можно ускорить алгоритм (возможно, с потерей точности — здесь точность не особо важна, как видите, задача не особо формализована)
Может ли такой алгоритм, в принципе, применяться на практике, при заданных ограничениях (не слишком ли он сложный)?

PS. По моему, похожая задача решается в системах контроля версий. Главное отличие моей задачи в том, что может поменяться одновременно и фрагмент и окружающий текст.

Здравствуйте, Аноним, Вы писали:

А>Есть текст, есть цитата из него.

я бы сделал так: в цитате поотбрасывал окончания (вполне достаточно взять стемер типа snowball), для каждого слова посчитал хеш и хранил бы вектор этих хешей как ключ цитаты. при поиске максимального совпадения исходный текст также прогоняется через стемер и хеш-функцию. после чего с помошью левенштейна и какойто матери вполне можно найти фрагмент текста совпадающий с цитатой с точностью до расстояния редактирования. поиск можно оптимизировать учитывая что тебя наврядли будут интересовать фрагменты _сильно_ отличающиеся от цитаты (т.е. расстояние редактирования большое).
единственное что этот метод не учитывает ошибки/корректуру в словах. в принципе можно и это учесть но процесс усложняется.

Здравствуйте, Аноним, Вы писали:

А>Есть текст, есть цитата из него.
...

Пометь символы цитаты. То есть помимо кода символа храни вспомогательный код (tag).
Например текст представь в виде utf не помеченный текст от uc4: 0x00000..0x0FFFF а помеченный uc4: 0x10000..0x1FFFF.
Или если веб то например так <span class="cit">Есть текст, есть цитата из него</span>. Или просто цветом выдели.
Единственное но, придётся делать редактор такого текста, да и историю редактирования можно хранить.

А так можеш разбить на группы по N слова (где то ~3) и ввести растояние (например Ливинштейна) выделить ближайшие и их и подчеркивать.

Представь взял я цитату и произвольно перемешал слова или переставил предложения изменив смысл, или просто передвинул запятую (казнить нельзя помиловать).
И уже не цитата, а ремикс

ps: в ситемах контроля версий сравниваются строки текста, а не цитаты.

Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, Аноним, Вы писали:

А>>Есть текст, есть цитата из него.
А>...

А>Пометь символы цитаты. То есть помимо кода символа храни вспомогательный код (tag).
А>Например текст представь в виде utf не помеченный текст от uc4: 0x00000..0x0FFFF а помеченный uc4: 0x10000..0x1FFFF.
А>Или если веб то например так <span class="cit">Есть текст, есть цитата из него</span>. Или просто цветом выдели.
А>Единственное но, придётся делать редактор такого текста, да и историю редактирования можно хранить.

Интересная идея (например, пометить начало и конец цитированного фрагмента какими-нибудь невидимым служебным символом из unicode (рассчитывается что редактирование производится в обычной textarea и само редактирование мы не можем контролировать)). Тогда, если пользователь будет редактировать отдельно текст и этот фрагмент, то есть шанс, что эти символы останутся в нужном месте. Но есть недостаток: первоначальная задача — организовать "целостность по цитатам"
в множестве текстов, цитирующих друг друга. То есть, пользователь исправляет орфографические ошибки в своём тексте — происходит апдейт цитат во всех цитирующих текстах. А вставляя маркеры мы позволим пользователю произвольным образом менять цитаты в чужих текстах, что недопустимо. Тем более, если маркеры перепутаются, например, при copy-paste, будет бред. И ещё, этот способ не работает для большого количества цитат одного текста. И, последнее, прийдётся редактировать оригинальный текст при цитировании, а этого, по определённым соображениям, не хочется.

А>А так можеш разбить на группы по N слова (где то ~3) и ввести растояние (например Ливинштейна) выделить ближайшие и их и подчеркивать.

А>Представь взял я цитату и произвольно перемешал слова или переставил предложения изменив смысл, или просто передвинул запятую (казнить нельзя помиловать).
А>И уже не цитата, а ремикс

Согласен — как раз в таких случаях надо выводить что-нибудь типа "цитата не проверена", и это поможет, когда цитируют с коверканием смысла или даже намеренно добавляют ошибки в текст (бывает такое) (предполагается, что все "правильные" цитаты производятся исключительно точным копированием фрагмента).

Здравствуйте, Аноним, Вы писали:

А>Интересная идея (например, пометить начало и конец цитированного фрагмента какими-нибудь невидимым служебным символом из unicode (рассчитывается что редактирование производится в обычной textarea и само редактирование мы не можем контролировать)). Тогда, если пользователь будет редактировать отдельно текст и этот фрагмент, то есть шанс, что эти символы останутся в нужном месте.

Вообще-то можно вычислять самую короткую последовательность правок, которая переводит исходный текст в конечный.
А потом применять эту последовательность к размеченному сколь угодно тексту...

Здравствуйте, Erop, Вы писали:

E>Здравствуйте, Аноним, Вы писали:

А>>Интересная идея (например, пометить начало и конец цитированного фрагмента какими-нибудь невидимым служебным символом из unicode (рассчитывается что редактирование производится в обычной textarea и само редактирование мы не можем контролировать)). Тогда, если пользователь будет редактировать отдельно текст и этот фрагмент, то есть шанс, что эти символы останутся в нужном месте.

E>Вообще-то можно вычислять самую короткую последовательность правок, которая переводит исходный текст в конечный.
E>А потом применять эту последовательность к размеченному сколь угодно тексту...

Спасибо, похоже, это и есть оптимальное (вернее, достаточно простое) решение! (при допущении, что известен предыдущий вариант текста, то есть, апдейт/поиск цитат выполняется при обновлении цитируемого текста — я забыл об этом упомянуть; а если предыдущий вариант текста недоступен, то есть, при "асинхронном" обновлении цитат, такого вроде не получится. Но задача асинхронного обновления цитат всё равно имеет значение — например, если цитаты берутся со страниц с удалённых серверов, так что, вопрос остаётся открытым.)

То есть, решение такое:
— указатель на цитату в тексте — это смещение от начала текста и длина цитаты
— при редактировании текста вычисляем минимальный скрипт редактирования
— достаём все указатели на цитаты для редактируемого текста
— для каждой цитаты, из скрипта редактирования текста, получаем скрипт редактирования цитаты
— редактируем полученным скриптом каждую цитату
— (а если скрипт редактирования цитаты слишком большой, пишем, что цитата не найдена)