PHP Ngrams comparing two arrays Is there some more efficient way to calculate and extract that array that is greater than or equal to 0.8.

I had to use two foreach to do it, which is not very performant.

The idea is to find the most similar expressions comparing this two arrays.

Thanks!

function getNgrams($match, $n = 2) {

            $ngrams = array();
            $len = strlen($match);
            for($i = 0; $i &lt; $len; $i++) {
                    if($i &gt; ($n - 2)) {
                            $ng = '';
                            for($j = $n-1; $j &gt;= 0; $j--) {
                                    $ng .= $match[$i-$j];
                            }
                            $ngrams[] = $ng;
                    }

            }
            return $ngrams;

    }


$question = 'happy birthday';
$rta = array('today', ' tomorrow ', 'monday', 'birthda');

$question_array = explode(' ',($question));
#print_r($question_array);


$ngram_question = array_map("getNgrams",$question_array);
$ngram_rta = array_map("getNgrams",$rta);
#print_r($ngram_rta);


foreach ($rta as &amp;$valor) { 

    foreach ($question_array as &amp;$valorq) {

        $ngram_rta = getNgrams($valor);
        $ngram_q = getNgrams($valorq);

        if ((sizeof(array_intersect($ngram_rta,$ngram_q))/sizeof($ngram_rta)) &gt;= 0.8)
            {echo $valor;
             echo "&lt;br&gt;";
            }

    }
}
I'm pretty sure I don't understand the usage of your script, but I'll assume you have a good reason for performing this comparison.

I see that you are declaring/calling $ngram_rta = getNgrams($valor) inside your inner loop.  This means that for each word in your question string, you are asking php to do the same job to produce the same output.  You must not ask php to repeat itself.  Since $ngrame_rta is not mutated inside of the inner loop, you should generate the data inside the outer loop and count its length before entering the inner loop.



In your posted script, if($i &gt; ($n - 2)) { is never satisfied on the first iteration.  I'll urge you to have a re-think about this condition.  Perhaps you want to make the 2 dynamic and perhaps you want to change the comparison to &gt;=.  You decide how to avoid performing an usable iteration.



If the idea here is to break a word into an array of strings with $n length starting from each offset in the string then this seems cleaner:

(Demo)

for ($pos = strlen($match) - $n; $pos &gt;= 0; --$pos) {
    $nGrams[] = substr($match, $pos, $n);
}




I guess your script could boil down to something like this:

(Demo)

function getNgrams($match, $n = 2) {
    $nGrams = [];
    for ($pos = strlen($match) - $n; $pos &gt;= 0; --$pos) {
        $nGrams[] = substr($match, $pos, $n);
    }
    return $nGrams;
}

$question = 'happy birthday';
$questionNGrams = array_map("getNgrams", explode(' ', $question));

$rta = ['today', 'happy', ' tomorrow ', 'monday', 'birthda'];

foreach ($rta as $value) { 
    $rtaNGram = getNgrams($value);
    $rtaNGramCount = count($rtaNGram);
    foreach ($questionNGrams as $questionNGram) {
        if (count(array_intersect($rtaNGram, $questionNGram)) / $rtaNGramCount &gt;= 0.8) {
            echo "{$value}&lt;br&gt;";
            break;  // prevent further iteration of inner loop after $value qualifies
        }
    }
}


Output:

happy&lt;br&gt;birthda&lt;br&gt;


I do find my eyes going a bit crossed as I continue to read your code because I don't relate $question and $rta to the data they contain.  Perhaps be more accurate/intentional about the variable naming.