find matching link in text file with php

Question

I have a function to read a text file and cross match with a directory search to maths the descriptions (text file) with a directory index for files. I used the leveltensin function to give some fuzzy logic so names don't need to be 100% identical but i'm running into a snag, as I have it set up now i'm hetting a memory wall because when i uncomment the lines below it searches the entire txt file and compares every single ling against the directory file name. With over 700 files each being checked 700 times i quickly run out of memory. i need some way to jump out of the while (!feof($file_handle) ) when it finds a match then find some way to set the starting point for the next pass to the line position we stopped it so it isint looping 0-700 every single time

function GenerateList($titleB, $descB, $thumbB, $dirB, $patternB){
$outputB = "<CATEGORY name=\"$titleB\" desc=\"$descB\" thumb=\"$thumbB\">";
$open_error = 0;

if (is_dir($dirB)){
$myDirectory = opendir($dirB);
// get each entry
while($entryName = readdir($myDirectory)) {
    $dirArray[] = $entryName;
}

// close directory
closedir($myDirectory);

//  count elements in array
$indexCount = count($dirArray);

// sort em
sort($dirArray);
// loop through the array of files and print them all
if (!($text = file_get_contents("Scripts/descriptions.txt"))){$open_error = 1;}
$results = array();
for($index=0; $index < $indexCount; $index++) {
    $ext = explode(".", $dirArray[$index]);
    $parsed_title = preg_replace ($patternB, "", $ext[0]);
    if ((substr("$dirArray[$index]", 0, 1) != ".")&&($ext[1] == "flv")){ // don't list hidden files

//if ($open_error == 0){
//  $file_handle = fopen("Scripts/descriptions.txt", "rb");

//while (!feof($file_handle) ) {
//$line_of_text = fgets($file_handle);
//$parts = explode('|', $line_of_text);
/*
echo "<PRE>";
echo strtolower($parts[0]);
echo "</br>";
echo strtolower($parsed_title);
echo "</br>";
echo "</PRE>";
*/
//if ((wordMatch(strtolower($parts[0]), strtolower($parsed_title), 2)) > 0){
        $outputB .= "<ITEM>";
        $outputB .= "<file_path>/Sources/Power Rangers/$dirB".$dirArray[$index]."</file_path>";
        $outputB .= "<file_width>500</file_width>";
        $outputB .= "<file_height>375</file_height>";
        $outputB .= "<file_title>".$parsed_title."</file_title>";
//      $outputB .= "<file_desc>".$parts[1]."</file_desc>";
        $outputB .= "<file_desc>test</file_desc>";
//      $outputB .= "<file_image>".$match_result[2]."</file_image>";
        $outputB .= "<file_image>$thumbB</file_image>";
//      $outputB .= "<featured_image>".$match_result[3]."</featured_image>";
        $outputB .= "<featured_image>$thumbB</featured_image>";
//      $outputB .= "<featured_or_not>".$parts[4]."</featured_or_not>";
        $outputB .= "<featured_or_not>true</featured_or_not>";
        $outputB .= "</ITEM>";
//};//if ((wordMatch($parts[0], strtolower($word), 2) > 0)
//};//while
//fclose($file_handle);

//};//if ($open_error == 0)
    };//if ((substr("$dirArray[$index]", 0, 1) != ".")&&($ext[1] == "flv"))
};//for($index=0; $index < $indexCount; $index++) 
};//if (file_exists($dirB))
$outputB .= "</CATEGORY>";
return $outputB;
};//function

    function wordMatch($words, $input, $sensitivity){ 
        $shortest = -1; 
        foreach ($words as $word) { 
            $lev = levenshtein($input, $word); 
            if ($lev == 0) { 
                $closest = $word; 
                $shortest = 0; 
                break; 
            } //if
            if ($lev <= $shortest || $shortest < 0) { 
                $closest  = $word; 
                $shortest = $lev; 
            } //if
        } //foreach
        if($shortest <= $sensitivity){ 
            return $closest; 
        } else { 
            return 0; 
        } //if/else
    } // function, http://php.net/manual/en/function.levenshtein.php

Answer 1

Instead of a regex, you can compute the edit distance between the two items. Your 80% heuristic would then be equivalent to saying that (length-edit_distance)/length >= .8 where length is the length of the string you're trying to match.

So if the string was 20 chars long and the edit distance from your target was 2, you would calculate that (20-2) / 20 == .9 In other words, that item was a 90% match to your target. That's higher than .8, so you accept it as a match.

Note that 'edit distance' is also known as Levenshtein distance, so you just do something like:

$len = (float) strlen($target);  // Avoids integer division.
$match = ($len-levenshtein($input, $target))/$len;

if ($match >= 0.8) {
  // The $input matches our $target
}