Учебник по основам PHP. PHPBeginner


Строковые функции - часть 10


См. также: егед(), strcasecmp(), substr(), stristr(), strcmp(), strncmp(), strncasecmp(), strnatcmp() и strstr().

simila_r text

Определение схожести двух строк

int similar_text (string first, string secOnd [, dOuble percent])

Функция вычисляет схожесть двух строк по алгоритму, описанному Оливером (Oliver [1993]). Но вместо стека (как в псевдокоде Оливера) она использует рекурсивные вызовы. Сложность алгоритма делает функцию медленной, и ее скорость пропорциональна (N3), где N — длина наибольшей строки.

Возвращается число символов, совпавших в обеих строках. При передаче по ссылке третьего необязательного аргумента в нем сохраняется процент совпадения строк.

levenshtein

Определение различия Левенштейна двух строк int levenshtein (string strl, string str2)

int levenshtein (string strl, string str2, int cOst_ins, int cOst_rep, int cOst_del)

int levenshtein (string strl, string str2. function cOst)

«Различие Левенштейна» — это минимальное число символов, которое требовалось бы заменить, вставить или удалить для того, чтобы превратить строку strl в str2. Сложность алгоритма пропорциональна произведению длин строк strl и str2 (это делает функцию более быстродействующей, чем similar_text()).

Первая форма функции возвращает число необходимых операций над символами строк для трансформации strl в str2.

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

Вариант три, который еще не реализован, позволит указывать функцию, используемую для расчета сложности трансформации. Функция cOst будет вызываться со следующими аргументами:

  • применяемая операция (вставить, изменить, удалить): «I», «R», «D»;
  • фактический символ первой строки;
  • фактический символ второй строки;
  • позиция строки 1;
  • позиция строки 2;
  • оставшаяся длина строки 1;
  • оставшаяся длина строки 2.

Вызываемая функция должна будет возвратить стоимость этой операции.




Начало  Назад  Вперед