public function match($input)
 {
     // no shortest distance found, yet
     $shortest = -1;
     // loop through words to find the closest
     foreach ($this->possibleTokens as $word) {
         // calculate the distance between the input word,
         // and the current word
         $lev = levenshtein($input, $word);
         // check for an exact match
         if ($lev == 0) {
             // closest word is this one (exact match)
             $closest = $word;
             $shortest = 0;
             // break out of the loop; we've found an exact match
             break;
         }
         // if this distance is less than the next found shortest
         // distance, OR if a next shortest word has not yet been found
         if ($lev <= $shortest || $shortest < 0) {
             // set the closest match, and shortest distance
             $closest = $word;
             $shortest = $lev;
         }
     }
     return $closet;
 }

 function find_similar_words($word, $threshold)
 {
     $similar = array();
     $word = addslashes(trim($word));
     $sndx = substr($word, 0, 2);
     $query = "select `word` from `{$this->tbl}` where `di`=?";
     @($result = $this->query($query, array($sndx)));
     while ($res = $result->fetchRow(DB_FETCHMODE_ASSOC)) {
         $tword = $res["word"];
         $lev = levenshtein($tword, $word);
         if (count($similar) < $threshold) {
             $similar[$tword] = $lev;
             asort($similar);
         } else {
             // If the array is full then if the lev is better than the worst lev
             // then update
             $keys = array_keys($similar);
             $last_key = $keys[count($keys) - 1];
             if ($lev < $similar[$last_key]) {
                 unset($similar[$last_key]);
                 $similar[$tword] = $lev;
                 asort($similar);
             }
         }
     }
     return $similar;
 }

 /**
  * handler for 404 (page not found) error
  *
  * @param string $sUrl url which was given, can be not specified in some cases
  *
  * @return void
  */
 public function handlePageNotFoundError($sUrl = '')
 {
     // module active?
     if (!oxRegistry::getConfig()->getConfigParam("psRedirect404_status")) {
         return parent::handlePageNotFoundError($sUrl = '');
     }
     $iShortest = -1;
     $iHeaderType = 302;
     $sSearchString = $this->_clearUrl($sUrl);
     // psRedirect404
     // checks based on levenshtein algorithm closest url from
     // oxid seo urls (oxseo) and redirect with header 302 to this page
     try {
         foreach ($this->_getSeoUrls() as $value) {
             $sUrl = $this->_clearUrl($value[0]);
             $sLevRes = levenshtein($sSearchString, $sUrl);
             #echo $sLevRes." - ".$sUrl." (".$value[0].")<br>";
             if ($sLevRes <= $iShortest || $iShortest < 0) {
                 $sClosest = $value[0];
                 $iShortest = $sLevRes;
                 if ($sLevRes <= 10 && oxRegistry::getConfig()->getConfigParam("psRedirect404_redirecttype") == "auto") {
                     $iHeaderType = 301;
                 }
             }
         }
         if (!oxRegistry::getConfig()->getConfigParam("psRedirect404_redirecttype") == "301") {
             $iHeaderType = 301;
         }
         oxRegistry::getUtils()->redirect(oxRegistry::getConfig()->getShopUrl() . $sClosest, false, $iHeaderType);
     } catch (Exception $e) {
     }
     $this->showMessageAndExit("Found");
 }

 public function process(ContainerBuilder $container)
 {
     $compiler = $container->getCompiler();
     $formatter = $compiler->getLoggingFormatter();
     $tags = array_unique(array_merge($container->findTags(), $this->whitelist));
     foreach ($container->findUnusedTags() as $tag) {
         // skip whitelisted tags
         if (in_array($tag, $this->whitelist)) {
             continue;
         }
         // check for typos
         $candidates = array();
         foreach ($tags as $definedTag) {
             if ($definedTag === $tag) {
                 continue;
             }
             if (false !== strpos($definedTag, $tag) || levenshtein($tag, $definedTag) <= strlen($tag) / 3) {
                 $candidates[] = $definedTag;
             }
         }
         $services = array_keys($container->findTaggedServiceIds($tag));
         $message = sprintf('Tag "%s" was defined on service(s) "%s", but was never used.', $tag, implode('", "', $services));
         if (!empty($candidates)) {
             $message .= sprintf(' Did you mean "%s"?', implode('", "', $candidates));
         }
         $compiler->addLogMessage($formatter->format($this, $message));
     }
 }

 function compare($debug = false)
 {
     $first = $this->str1;
     $second = $this->str2;
     $this->levenshtein = levenshtein($first, $second);
     $this->similarity['value'] = $sim = similar_text($first, $second, $perc);
     $this->similarity['percentage'] = $perc;
     if ($debug) {
         echo "{$first} | {$second}<br>";
         echo "leven: " . $this->levenshtein;
         echo '<br>similarity: ' . $sim . ', ' . $perc . '%<br><br>';
     }
     $soundex1 = soundex($first);
     $soundex2 = soundex($second);
     $this->soundex['levenshtein'] = levenshtein($soundex1, $soundex2);
     $this->soundex['similarity'] = $sim = similar_text($soundex1, $soundex2, $perc);
     $this->soundex['percentage'] = $perc;
     if ($debug) {
         echo "Soundex: " . $soundex1 . ", " . $soundex2 . "<BR>";
         echo 'levenshtein: ' . $this->soundex['levenshtein'] . '<br>';
         echo 'similarity: ' . $sim . ', ' . $perc . '%<br><br>';
     }
     $m1 = metaphone($first);
     $m2 = metaphone($second);
     $this->metaphone['levenshtein'] = levenshtein($m1, $m2);
     $this->metaphone['similarity'] = $sim = similar_text($m1, $m2, $perc);
     $this->metaphone['percentage'] = $perc;
     if ($debug) {
         echo "metaphone: " . $m1 . ", " . $m2 . "<br>";
         echo 'levenshtein: ' . $this->metaphone['levenshtein'] . '<br>';
         echo 'similarity: ' . $sim . ', ' . $perc . '%<br>';
         echo '<br>-------------------<br>';
     }
 }

function findClosest1($input = 0, $numbers)
{
    // array of numbers to check
    sort($numbers);
    // no shortest distance found, yet
    $shortest = -1;
    // loop through numbers to find the closest
    foreach ($numbers as $num) {
        // calculate the distance between the input num,
        // and the current num
        $lev = levenshtein($input, $num);
        // check for an exact match
        if ($lev == 0) {
            // closest num is this one (exact match)
            $closest = $num;
            $shortest = 0;
            // break out of the loop; we've found an exact match
            break;
        }
        // if this distance is less than the next found shortest
        // distance, OR if a next shortest num has not yet been found
        if ($lev <= $shortest || $shortest < 0) {
            // set the closest match, and shortest distance
            $closest = $num;
            $shortest = $lev;
        }
    }
    echo "Closest number is: " . $closest;
}

 private function levenshteinDistance($input, $words)
 {
     $shortest = -1;
     $closest = [];
     foreach ($words as $key => $word) {
         $lev = levenshtein($input, explode(' ', $word)[0]);
         if ($lev == 0 && count(explode(' ', $word)) == 1) {
             return $word;
         }
         if ($lev <= $shortest || $shortest < 0) {
             $closest[] = [$word, $lev, $key];
             $shortest = $lev;
         }
     }
     $top4 = array_slice(array_reverse($closest), 0, 3);
     foreach ($top4 as $key => $item) {
         if ($item[1] > 3) {
             unset($top4[$key]);
         }
     }
     if (count($top4) == 1) {
         return reset($top4)[0];
     }
     return count($top4) > 0 ? $top4 : false;
 }

 /**
  *
  * @param string $word
  * @param array $words
  * @return array
  */
 public static function similarWord($word, array $words)
 {
     $similarity = config('pages.similar.similarity');
     $metaSimilarity = 0;
     $minLevenshtein = 1000;
     $metaMinLevenshtein = 1000;
     $result = [];
     $metaResult = [];
     foreach ($words as $n) {
         $minLevenshtein = min($minLevenshtein, levenshtein($n, $word));
     }
     foreach ($words as $n => $k) {
         if (levenshtein($k, $word) <= $minLevenshtein) {
             if (similar_text($k, $word) >= $similarity) {
                 $result[$n] = $k;
             }
         }
     }
     foreach ($result as $n) {
         $metaMinLevenshtein = min($metaMinLevenshtein, levenshtein(metaphone($n), metaphone($word)));
     }
     foreach ($result as $n) {
         if (levenshtein($n, $word) == $metaMinLevenshtein) {
             $metaSimilarity = max($metaSimilarity, similar_text(metaphone($n), metaphone($word)));
         }
     }
     foreach ($result as $n => $k) {
         if (levenshtein(metaphone($k), metaphone($word)) <= $metaMinLevenshtein) {
             if (similar_text(metaphone($k), metaphone($word)) >= $metaSimilarity) {
                 $metaResult[$n] = $k;
             }
         }
     }
     return $metaResult;
 }

 /**
  * {@inheritdoc}
  */
 public function get($name)
 {
     $name = strtolower($name);
     if (!array_key_exists($name, $this->parameters)) {
         if (!$name) {
             throw new ParameterNotFoundException($name);
         }
         $alternatives = array();
         foreach ($this->parameters as $key => $parameterValue) {
             $lev = levenshtein($name, $key);
             if ($lev <= strlen($name) / 3 || false !== strpos($key, $name)) {
                 $alternatives[] = $key;
             }
         }
         $nonNestedAlternative = null;
         if (!count($alternatives) && false !== strpos($name, '.')) {
             $namePartsLength = array_map('strlen', explode('.', $name));
             $key = substr($name, 0, -1 * (1 + array_pop($namePartsLength)));
             while (count($namePartsLength)) {
                 if ($this->has($key)) {
                     if (is_array($this->get($key))) {
                         $nonNestedAlternative = $key;
                     }
                     break;
                 }
                 $key = substr($key, 0, -1 * (1 + array_pop($namePartsLength)));
             }
         }
         throw new ParameterNotFoundException($name, null, null, null, $alternatives, $nonNestedAlternative);
     }
     return $this->parameters[$name];
 }

function correct_word($mot, $dictionnaire)
{
    $mot_entre = strtolower($mot);
    if (in_array($mot_entre, $dictionnaire)) {
        $faute = false;
        $correction = false;
    } else {
        //Si le mot n'est pas dans le dictionnaire
        $distance = -1;
        //On va rechercher des distances de mots : pour l'instant, elle est à moins un.
        $suggestions = array();
        foreach ($dictionnaire as $mot_dico) {
            $lev = levenshtein($mot_entre, $mot_dico);
            if ($lev <= 2) {
                $faute = true;
                $correction = true;
                $suggestions[$lev] = $mot_dico;
            }
        }
        if (!isset($faute)) {
            //Si il n'existe aucun mot à correspondance exacte et si le mot est trop éloigné du dico
            $faute = true;
            $correction = false;
        }
    }
    if ($faute && $correction) {
        ksort($suggestions);
        $return = current($suggestions);
    } elseif ($faute && !$correction) {
        $return = $mot;
    } else {
        $return = $mot;
    }
    return $return;
}

 public function closest($input, array $words)
 {
     // no shortest distance found, yet
     $shortest = -1;
     $match = [];
     // loop through words to find the closest
     foreach ($words as $word) {
         // calculate the distance between the input word,
         // and the current word
         $lev = levenshtein(strtolower($input), strtolower($word), 1, 2, 3);
         // check for an exact match
         if ($lev == 0) {
             // closest word is this one (exact match)
             $match = [$word];
             // $closest = $word;
             $shortest = 0;
             // break out of the loop; we've found an exact match
             break;
         }
         // if this distance is less than the next found shortest
         // distance, OR if a next shortest word has not yet been found
         if ($lev < $shortest || $shortest < 0) {
             // set the closest match, and shortest distance
             $match = [$word];
             // $closest = $word;
             $shortest = $lev;
         } elseif ($lev == $shortest) {
             $match[] = $word;
         }
     }
     if ($shortest > 6) {
         return [];
     }
     return $match;
 }

 public function correct($word, $dictionary)
 {
     if (strlen($word) < 255) {
         $word = strtolower($word);
         if (isset($dictionary[$word])) {
             return $word;
         }
         $edits1 = $edits2 = array();
         foreach ($dictionary as $dictWord => $count) {
             $dist = levenshtein($word, $dictWord);
             if ($dist == 1) {
                 $edits1[$dictWord] = $count;
             } else {
                 if ($dist == 2) {
                     $edits2[$dictWord] = $count;
                 }
             }
         }
         if (count($edits1)) {
             arsort($edits1);
             return key($edits1);
         } else {
             if (count($edits2)) {
                 arsort($edits2);
                 return key($edits2);
             }
         }
     } else {
         $word = '';
     }
     return $word;
 }

 /**
  * This method manages the session fingerprint
  *
  * Check current client Fingerprint against the values saved in the session.
  * Save the current Fingerprint to the session
  * Rate the fingerprint match pass/fail based on any changes
  * On fail, clear the session, leaving only the new client fingerprint
  *
  * @param AttributeInterface $session session manager object or another
  *                                    AttributeInterface implementing object
  *
  * @return bool true if matched, false if not
  */
 public function checkSessionPrint(AttributeInterface $session)
 {
     $score = 0;
     // combined levenshtein distance of changes
     $changes = 0;
     // number of changed fields
     $currentFingerprint = $this->takePrint();
     $savedFingerprint = unserialize($session->get('SESSION_FINGERPRINT'));
     if ($savedFingerprint === false) {
         $savedFingerprint = $currentFingerprint;
         $changes = empty($_SESSION) ? 0 : 3;
         // in a populated session - force fail;
     }
     foreach ($currentFingerprint as $key => $current) {
         $distance = levenshtein($current, $savedFingerprint[$key]);
         $score += $distance;
         $changes += $distance > 0 ? 1 : 0;
     }
     $return = true;
     // if more than one field changed, or if that change is a distance greater than 30, fail it.
     if ($changes > 1 || $score > 30) {
         $session->clear();
         // session data should not be preserved
         $return = false;
     }
     $session->set('SESSION_FINGERPRINT', serialize($currentFingerprint));
     return $return;
 }

function output_remote_mfg_options($mfgs, $levenshtein = false, $id = false)
{
    $outputs = array();
    $copies = $mfgs;
    if (!empty($levenshtein)) {
        while (!empty($copies)) {
            $key = null;
            $distance = PHP_INT_MAX;
            foreach ($copies as $jj => $copy) {
                $lev = levenshtein($copy['mf_name'], $levenshtein);
                if ($lev < $distance) {
                    $key = $jj;
                    $distance = $lev;
                }
            }
            $outputs[] = $copies[$key];
            unset($copies[$key]);
            $copies = array_values($copies);
        }
    } else {
        $outputs = $mfgs;
    }
    //echo "<select name='maps' id="">";
    $c = 0;
    foreach ($outputs as $mfg) {
        $selected = '';
        if ($mfg['manufacturer_id'] == $id || $id === false && $c === 0) {
            $selected = " selected='selected'";
            $c += 1;
        }
        echo "<option value='{$mfg['manufacturer_id']}'{$selected}>{$mfg['mf_name']}</option>";
    }
    //echo "</select>";
}

function MakeSuggestion($keyword, $ln)
{
    $trigrams = BuildTrigrams($keyword);
    $query = "\"{$trigrams}\"/1";
    $len = strlen($keyword);
    $delta = LENGTH_THRESHOLD;
    $weight = 'weight()';
    if (SPHINX_20 == true) {
        $weight = '@weight';
    }
    $stmt = $ln->prepare("SELECT *, {$weight} as w, w+:delta-ABS(len-:len) as myrank FROM suggest WHERE MATCH(:match) AND len BETWEEN :lowlen AND :highlen\r\n\t\t\tORDER BY myrank DESC, freq DESC\r\n\t\t\tLIMIT 0,:topcount OPTION ranker=wordcount");
    $stmt->bindValue(':match', $query, PDO::PARAM_STR);
    $stmt->bindValue(':len', $len, PDO::PARAM_INT);
    $stmt->bindValue(':delta', $delta, PDO::PARAM_INT);
    $stmt->bindValue(':lowlen', $len - $delta, PDO::PARAM_INT);
    $stmt->bindValue(':highlen', $len + $delta, PDO::PARAM_INT);
    $stmt->bindValue(':topcount', TOP_COUNT, PDO::PARAM_INT);
    $stmt->execute();
    if (!($rows = $stmt->fetchAll())) {
        return false;
    }
    // further restrict trigram matches with a sane Levenshtein distance limit
    foreach ($rows as $match) {
        $suggested = $match["keyword"];
        if (levenshtein($keyword, $suggested) <= LEVENSHTEIN_THRESHOLD) {
            return $suggested;
        }
    }
    return $keyword;
}

 function getDidyoumeanText()
 {
     Mage::getSingleton('catalogsearch/fulltext')->prepareResult();
     $search = Mage::getModel('catalogsearch/Mysql4_fulltext_collection');
     $search->addAttributeToSelect(Mage::getSingleton('catalog/config')->getProductAttributes());
     $search->loadData();
     $bestMatch = array();
     $input = Mage::helper('catalogsearch')->getQueryText();
     foreach ($search as $search1) {
         $words1 = explode(" ", $search1->getName());
         for ($k = 0; $k < count($words1); $k++) {
             $keyword = $words1[$k];
             $str1 = strtolower($keyword);
             $str2 = strtolower($input);
             $lev = levenshtein($str1, $str2, 1, 1, 1);
             if (isset($keyword) && trim($keyword) != "") {
                 $bestMatch[$lev][] = $keyword;
             }
             if (!isset($lowest) || $lev < $lowest) {
                 $lowest = $lev;
             }
         }
     }
     return array_unique($bestMatch[$lowest]);
 }

function relevanssi_didyoumean($query, $pre, $post, $n = 5)
{
    global $wpdb, $relevanssi_variables, $wp_query;
    $total_results = $wp_query->found_posts;
    if ($total_results > $n) {
        return;
    }
    $q = "SELECT query, count(query) as c, AVG(hits) as a FROM " . $relevanssi_variables['log_table'] . " WHERE hits > 1 GROUP BY query ORDER BY count(query) DESC";
    $q = apply_filters('relevanssi_didyoumean_query', $q);
    $data = $wpdb->get_results($q);
    $distance = -1;
    $closest = "";
    foreach ($data as $row) {
        if ($row->c < 2) {
            break;
        }
        $lev = levenshtein($query, $row->query);
        if ($lev < $distance || $distance < 0) {
            if ($row->a > 0) {
                $distance = $lev;
                $closest = $row->query;
                if ($lev == 1) {
                    break;
                }
                // get the first with distance of 1 and go
            }
        }
    }
    if ($distance > 0) {
        $url = get_bloginfo('url');
        $url = esc_attr(add_query_arg(array('s' => urlencode($closest)), $url));
        $url = apply_filters('relevanssi_didyoumean_url', $url);
        echo "{$pre}<a href='{$url}'>{$closest}</a>{$post}";
    }
}

 public function match(&$collection, $needle, $tolerance)
 {
     $best = $tolerance;
     $match = '';
     $needle_chars = count_chars($needle);
     foreach ($collection as $userAgent) {
         $ua_chars = count_chars($userAgent);
         $sum = 0;
         $can_apply_ld = true;
         //Check from 32 (space) to 122 ('z')
         for ($i = 32; $i < 122; $i++) {
             $sum += abs($needle_chars[$i] - $ua_chars[$i]);
             if ($sum > 2 * $tolerance) {
                 $can_apply_ld = false;
                 break;
             }
         }
         if ($can_apply_ld === true) {
             $current = levenshtein($needle, $userAgent);
             if ($current <= $best) {
                 $best = $current - 1;
                 $match = $userAgent;
             }
         }
     }
     return $match;
 }

 /**
  * {@inheritdoc}
  */
 public function handleError(array $error, FatalErrorException $exception)
 {
     preg_match('/^Call to undefined method (.*)::(.*)\\(\\)$/', $error['message'], $matches);
     if (!$matches) {
         return;
     }
     $className = $matches[1];
     $methodName = $matches[2];
     $message = sprintf('Attempted to call method "%s" on class "%s".', $methodName, $className);
     $candidates = array();
     foreach (get_class_methods($className) as $definedMethodName) {
         $lev = levenshtein($methodName, $definedMethodName);
         if ($lev <= strlen($methodName) / 3 || false !== strpos($definedMethodName, $methodName)) {
             $candidates[] = $definedMethodName;
         }
     }
     if ($candidates) {
         sort($candidates);
         $last = array_pop($candidates) . '"?';
         if ($candidates) {
             $candidates = 'e.g. "' . implode('", "', $candidates) . '" or "' . $last;
         } else {
             $candidates = '"' . $last;
         }
         $message .= ' Did you mean to call ' . $candidates;
     }
     return new UndefinedMethodException($message, $exception);
 }

 public static function get_link($movieId)
 {
     $link = self::find_by_id($movieId);
     $exists = $link ? true : false;
     if ($link && days_from_now($link->timestamp) < LINK_UPDATE_DAYS) {
         // good
     } else {
         $exists = $link ? true : false;
         $movie = Movie::find_by_id($movieId);
         $link = new YouTube();
         $link->id = $movieId;
         $link->timestamp = gen_timestamp();
         $title = urlencode($movie->title);
         $endpoint = "https://www.googleapis.com/youtube/v3/search?part=snippet&maxResults=10&q={$title}&type=video&videoCategoryId=30&key=AIzaSyBOaDIBNUCfbthPQ0XSZScnqI8jyxJ9G5Q";
         $m = self::getData($endpoint);
         foreach ($m->items as $mov) {
             $desc = $mov->snippet->description;
             if (levenshtein($title, $mov->snippet->title) < 2) {
                 foreach ($castArr as $actor) {
                     if (strpos($desc, $actor) !== false) {
                         $link->videoId = $mov->id->videoId;
                         break 2;
                         // break out of both foreach loops
                     }
                 }
             }
         }
         if ($exists) {
             $link->update();
         } else {
             $link->create();
         }
     }
     return $link;
 }