Портировать алгоритм сравнений строк с PHP на C/C++?

Question

[fruitbooter]

Про алгоритм

Описание и примеры алгоритма можно найти здесь, а его реализацию на GitHub (Gist)



Проблема

Столкнулся с тем, что алгоритм сам по себе медленный (в сравнении со встроенной в PHP функцией similar_text() в десятки раз медленнее), но имхо, качественный.


Причина, по которой не подошла готовая similar_text() её качество (опытный путь). Появилась мысль преобразовать её в собранную программу в надежде на увеличение скорости работы.

Неудачные мои варианты решений

— Хотел применить HipHop PHP, но не осилил установку на 32-битной машине.

— Пробовал написать самому, но осознал, что знаний не достаточно.

Итог

Надеюсь, что кому-то пригодится вариант этого алгоритма на PHP, и буду очень благодарен тем, кто заинтересуется и поможет преобразовать его в C/C++.

Answer 1

[zizop]

Если вам необходим более быстрый алгоритм поиска подстрок (ну и как следствие — сравнение строк), вы можете попробовать PHP расширение, написанное на C — Fast String Search. В неё используется алгоритм Комменца-Вальтера по аналогии с автоматом Ахо-Корасик, является модификацией алгоритма БМ для множества паттернов.

Может быть такой вариант вам подойдёт. Если же нет — пишите в личку, у меня где-то было исчерпывающее руководство по созданию Hello World расширения для PHP на C, с созданием своей функции, в которую можно впихнуть ваш алгоритм.

Comments

[fruitbooter]

Хочу поблагодарить за идею написания PHP расширения. Вот собственно и сам результат.

Вот в этой заметке частично можно понять, почему мне не подходил similar_text().

[zizop]

Отлично, рад что смог вам помочь!

Answer 2

[Константин]

Может вот это подойдёт? cz.php.net/manual/en/function.levenshtein.php

Comments

[Константин]

Также могу предложить Левенштайна на питоне, если хотите…

[fruitbooter]

levenshtein — его применение в исправлении ошибок в словах

[Константин]

Его применение — нахождение минимальной разницы букв между двумя стрингами. Зная длинну стринга, можно посчитать % совпадения.