Performing substitutions according to a word list in a database

Question

A bit of history

I had about 40,000 words in the database. I need words to correct the texts entered incorrectly by users. User enter text in any non-legal format and I use my words in the database to correct them. Everything was great before when when I had less than 50,000 words on my database. Now I have more than 100,000 words on the database.

What method do I use to correct words?

To start, I add all the words to a single database by query to the database. Example array with correct words:

$correctWords = array{
   "тоҷик",
   "ӯзбек",
   "қазоқ",
   "қирғиз"
   .......,
   "ғайратҷон"
}

With this array, I create another array by replacing some letters(ҷ,ӯ,қ,ғ to ч,у,к,г) with ordinary letters. In a result will be created an associative array from first array with correct words:

$wordBase = array{
   "точик"=>"тоҷик",
   "узбек"=>"ӯзбек",
   "казок"=>"қазоқ",
   "киргиз"=>"қирғиз"
   ................,
   "гайратчон"=>"ғайратҷон"
}

As you can see in the key of the array the wrong variants of words were transferred and the correct version of words was passed to the value of the array. From the text entered by users, I will search for words using words from the array key and replace them with a value to correct the text.

Usage wordbase array to correct incorrect typed words in the text:

$text = "Точик УЗБЕК казок КирГИЗ Гайратчон";

$dictionary = array{
   "точик"=>"тоҷик",
   "узбек"=>"ӯзбек",
   "казок"=>"қазоқ",
   "киргиз"=>"қирғиз"
   ................,
   "гайратчон"=>"ғайратҷон"
}

$output = preg_replace_callback("/\pL+/u", function ($m) use ($dictionary) {
$word = mb_strtolower($m[0]);
if (isset($dictionary[$word])) {
    $repl = $dictionary[$word];
    // Check for some common ways of upper/lower case
    // 1. all lower case
    if ($word === $m[0]) return $repl;
    // 2. all upper case
    if (mb_strtoupper($word) === $m[0]) return mb_strtoupper($repl);
    // 3. Only first letters are upper case
    if (mb_convert_case($word,  MB_CASE_TITLE) === $m[0]) return mb_convert_case($repl,  MB_CASE_TITLE);
    // Otherwise: check each character whether it should be upper or lower case
    for ($i = 0, $len = mb_strlen($word); $i < $len; ++$i) {
        $mixed[] = mb_substr($word, $i, 1) === mb_substr($m[0], $i, 1) 
            ? mb_substr($repl, $i, 1)
            : mb_strtoupper(mb_substr($repl, $i, 1));
    }
    return implode("", $mixed);
}
return $m[0]; // Nothing changes
}, $text);

echo $output;

Result

Тоҷик ӮЗБЕК қазоқ ҚирҒИЗ Ғайратҷон

When I have 100,000 words in the database, the function is to fix this text within 13-17 seconds. It takes a lot of time. What can I do to optimize the process of correcting the text with a large number of words? How not to use the whole word from the database to fix a few words? Now my code for fixing 2 words also uses the weight of an array of words and for 1000 words too I use the same. Can I solve the problem with queries on the database itself? If you need a large number of words for testing then please contact me. I will send them to you by reference.

Answer 1

This whole approach seems flawed to me. It's hard to predict how people will misspell words and you therefore end up with a very big list of possible misspellings.

Why not do it the traditional way: Start with a list of correct words ($correctWords), and use that to find the words not in that list. If you convert the text ($text), you want to correct, to an array of words you can use:

$textWords       = explode(' ',mb_strtolower($text));
$misspelledWords = array_diff($textWords,$correctWords);

I would remove punctuation before starting this process. When you have the possibly misspelled words, you can decide what to do with them.

You could, for instance, compare the misspelled words with the list of correct words, using one of these functions:

http://php.net/manual/en/function.levenshtein.php

http://php.net/manual/en/function.similar-text.php

The closest one is probably the correct one. This comparison might be slow, but there are probably only a few misspelled words, so it won't take long.

You could also still use your list of misspellings, if you want to.

After you've decided, what the misspelled words should be replace by, you can do:

$text = str_replace($misspelledWord,$replacementWord,$text);

Note that str_replace() will accept arrays, like this:

$text = str_replace($misspelledWords,$replacementWords,$text);

and after that you're done.

This only shows you the basic idea. It needs a lot of refinement to be of any practical use.