Соответствующие фрагменты в HTML-документе

Question

Кто-то подарил мне очень большой список копий, чтобы сделать длинный HTML-документ. Правки в формате:

«религиозный» должен быть «религия»
«их» должна быть «там»
«вы должны настойчивым» должны быть «вы должны быть стойким»

Скопированные были напечатаны вручную; в некоторых случаях «фактическое» значение слева не является точным соответствием для содержимого в документе. Порядок изменений обычно правильный, но даже это не гарантируется.

Это простая, но очень большая задача применить эти изменения вручную к документу. Я хотел бы автоматизировать процесс как можно больше, например. путем автоматического поиска фрагментов.

В длинном документе, подобном этому, я не могу просто искать все экземпляры «их» и заменить их «там». Иногда «их» использовались правильно, просто не в одном конкретном случае.

Другими словами, я ищу нечеткое текстовое совпадение, в котором порядок изменений влияет на поиск.

Что такое хороший подход к такой проблеме? Я надеюсь, что есть готовый проект с открытым исходным кодом, который может искать фрагменты в нечетком порядке.

Answer 1

Я не знаю ни одного инструмента. Но я бы использовал расстояние редактирования для обоих:

1. для неточного соответствия строк: возможно, std. Levenstein + swap (т.е. Damerau-Levenstein distance)
2. для точного соответствия последовательности: на этот раз возможно только с операциями Match и Swap. Вы можете использовать бесплатную (нулевую стоимость) Insert, чтобы получить слова, которые не следует редактировать.

Его не должно быть трудно реализовать. Но вычислительная сложность будет довольно высокой. Я бы использовал некоторые эвристики, чтобы пропустить безнадежные матчи. Предварительная обработка слов в документе и списке редактирования может быть хорошей: получите набор символов для каждого слова, чтобы дать возможность быстрого сравнения, прежде чем вычислять полное расстояние редактирования) и т. Д.