Как средствами PHP найти паттерн в предложении, в котором есть опечатка?

Question

[yurka]

Есть ли элегантный способ найти паттерн в предложении в котором присутствует этот паттер с опечаткой?

Паттерн может содержать от 1 до нескольких слов, если паттерн состоит из нескольких слов, то эти слова могут

быть без пробелов.


Пример: Найти паттерн «Поиск паттерна» в предложении «Функция, которая использует поескпатттерна»


На данных момент, решение которое я вижу, это: нужно создать массив со всеми комбинациями слов без пробелов («функция», «функциякоторая», «которая», «котораяиспользует»)

и проверять каждый токен функцией levenshtein с определенным порогом на ошибку (скажем с расстоянием не более 3), и выбирать наиболее подходящие.


Есть ли какое-либо более элегантное решение? Было бы классно иметь что то вроде:

preg_match_levenshtain($sentence,$pattern, $maxdistance);

Answer 1

[Rowdy Ro]

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

$pattern = 'Search pattern';
$sentence = 'Function, what uses searchpatttern';

$pattern = strtolower(str_replace(' ', '',$pattern));
$sentence = strtolower(str_replace(' ', '', $sentence));

$min = MAX_INT;
$index = -1;
for ($i = 0; $i < strlen($sentence) - strlen($pattern); ++$i) {
    $len = levenshtein($pattern, substr($sentence, $i, strlen($pattern) ));
    if ($len < $min) {
       // found
       $min = $len; 
       $index = $i;
    }
}

if ($min < THRESHOLD) {
 //found pattern at $index
}

Возможно достаточно убрать пробелы только из паттерна. Незабыть сохранить позиции пробелов, чтобы потом их вернуть на место.

Comments

[yurka]

Интересное решение, спасибо! Позиции пробелов можно будет сохранить, например, с помощью preg_match_all с PREG_OFFSET_CAPTURE

[slpdmn]

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

Answer 2

[shagguboy]

sphinx
habrahabr.ru/company/sphinx/blog/61807/