My text comparison algorithm works very slow

I tried to create an algorithm (Translation Memory) that finds similarities between texts and try to predict the closest possible translation of the text, but there is a big problem with the working time of the algorithm.

Example for 2.6ghz processor;

A match for "250(source) * 250(target) section" takes 3.36 seconds.
A match for "7000(source) * 250(target) section" takes 539.78 seconds.
A match for "7000(source) * 7000(target) section" takes 35042.76 seconds.


With the Match function, sentences in the source array are sorted by a loop. Then, the target arrays are listed underneath the loop. Thereafter, for each source sentence, the results in the target array are searched for the highest possible match.

This is matching function;

public function match($source,$target,$limit){ if(isset($source) && is_array($source) && count($source) > 0){

if(isset($target) && is_array($target) && count($target) > 0){$match = array() ;
$array = array(); foreach($source as $k =>$v){

$v = trim(preg_replace('/'.$this->regex.'/', null, $v));$similarity = $this->fetch($v,$target,$limit);

if($similarity[0]){$array[$k]['data'] =$similarity[1]['data'];
$array[$k]['match'] = $similarity[1]['match'];$match[] = $similarity[1]['match']; }else{$array[$k]['data'] = null;$array[$k]['match'] = null; } unset($source[$k]); } if(isset($match) && is_array($match) && count($match) > 0){
return array(true,$array,round((array_sum($match)/count($match)),2)); }else{ return array(true,$array,0);
}

}else{

return array(false,'source memory is empty');

}

}else{

return array(false,'source word is empty');

}

}


This is fetching function;

private function fetch($text,$array,$limit){$status = false;
$match = 0;$data = null;

foreach($array as$k1 => $v1){ foreach($v1 as $k2 =>$v2){

$old =$match;

$match =$this->similarity($text,$v2['source']);

if($match == 100){$data = $v2['target']; break; }elseif($match > $old){$data = $v2['target']; } unset($array[$k1][$k2]);

}

unset($array[$k1]);

}

if($match >=$limit){
$status = true; } return array($status,array('data'=>$data,'match'=>$match));

}


The matching algorithm calculates the similarity distance by breaking up the sentence into words (just like the matrix distance (Levenstein) algorithm that breaks the word into letters). Then, it exposes this distance as a percentage (For example, "I am going to school today" sentence is similar to "I am going home today" by %80).

This is similarity function;

private function similarity($source,$target){

$source = mb_strtolower($source,'UTF-8');
$target = mb_strtolower($target,'UTF-8');

$sourceAR = preg_split('/[\s]+/ui',$source);
$targetAR = preg_split('/[\s]+/ui',$target);

$sourceCount = count($sourceAR);
$targetCount = count($targetAR);

$difference = 0;$matrix = array_fill(0, $sourceCount + 1, array_fill(0,$targetCount + 1, 0));

for ($i = 1;$i < $sourceCount + 1;$i++){
$matrix[$i][0] = $i; } for ($j = 1; $j <$targetCount + 1; $j++){$matrix[0][$j] =$j;
}

/* $i = column / x axis*/ for ($i = 1; $i <=$sourceCount; $i++){ /*$j = row / y axis */
for ($j = 1;$j <= $targetCount;$j++){

/* calculation of cost (not match , missing/more) */
if($sourceAR[$i - 1] == $targetAR[$j - 1]){
$c = 0; }else{$c = 1;
}
/* calculation of cost (not match , missing/more) */

$matrix[$i][$j] = min($matrix[$i - 1][$j] + 1, $matrix[$i][$j - 1] + 1,$matrix[$i - 1][$j - 1] + $c);$difference = $matrix[$i][$j]; } /*$j = row / y axis */

}
/* $i = column / x axis */ return (100 - ((100*$difference)/\$sourceCount));

}


Since the algorithm is encoded with php, the solution must also be working with php.

At the output of the match; for each source sentence, the target sentence with the highest match and the percentage of this match must be given.

• this hurts my eyes. there's a built in function for this that i'm sure is a heck of a lot faster: similar_text. there's a built in function for levenshtein distance as well. – iwrestledabearonce Dec 23 '17 at 6:55
• How are you intending to treat occurrences of punctuation? Your preg_split () pattern means to split on whitespace characters (*character class brackets and i flag are not necessary) so all punctuation is stuck to its neighboring word. Is this satisfactory or do you also want to strip these characters off of the words? – mickmackusa Jan 14 '18 at 3:05