Расчет разницы в процентах двух файлов HTML

Question

Я пишу инструмент в php, который сравнивает файлы HTML и показывает различия. Теперь я ищу эффективный способ расчета разницы в процентах между двумя файлами HTML. Эти файлы могут быть произвольными (файлы у меня могут быть длиной до 300000 символов).

После некоторого исследования я наткнулся на расстояние Левенштейна, которое является алгоритмом O (n * m) и требует пространства O (n * m): версия php может поддерживать только до 255 символов, а моя собственная реализация O (n), было слишком медленным. После этого я попробовал функцию php аналогичного_текста, но этот алгоритм слишком медленный для очень больших HTML-файлов.

Итак, теперь я ищу еще один, более эффективный алгоритм для сравнения файлов HTML. Алгоритм аппроксимации также хорош. Может ли кто-нибудь дать мне несколько советов о том, как это сделать?

Answer 1

Вы можете установить расширение xdiff:

http://www.php.net/manual/en/function.xdiff-file-diff.php

Тогда получите диф двух файлов, и на основе этого дифф вы можете легко прийти с процентом.

Пример:

• Первый файл А: 400 слов
• Второй файл B: 400 слов

Diff Результаты: 200 слов Diff от А до Б

Это дало бы у вас 50% сходства.