Subversion Repositories cheapmusic

<?php namespace Fuse\Bitap;

function search($text, $pattern, $patternAlphabet, $options = [])
{
    $options = array_merge([
        'location' => 0,
        'distance' => 100,
        'threshold' => 0.6,
        'findAllMatches' => false,
        'minMatchCharLength' => 1
    ], $options);

    $expectedLocation  = $options['location'];
    // Set starting location at beginning text and initialize the alphabet.
    $textLen = mb_strlen($text);
    // Highest score beyond which we give up.
    $currentThreshold = $options['threshold'];
    // Is there a nearby exact match? (speedup)
    $bestLocation = mb_strpos($text, $pattern, $expectedLocation);

    $patternLen = mb_strlen($pattern);

    // a mask of the matches
    $matchMask = [];
    for ($i = 0; $i < $textLen; $i++) {
        $matchMask[$i] = 0;
    }

    if ($bestLocation !== false) {
        $score = score($pattern, [
            'errors' => 0,
            'currentLocation' => $bestLocation,
            'expectedLocation' => $expectedLocation,
            'distance' => $options['distance']
        ]);
        $currentThreshold = min($score, $currentThreshold);

        // What about in the other direction? (speed up)
        $bestLocation = mb_strrpos($text, $pattern, $expectedLocation + $patternLen);

        if ($bestLocation !== false) {
            $score = score($pattern, [
                'errors' => 0,
                'currentLocation' => $bestLocation,
                'expectedLocation' => $expectedLocation,
                'distance' => $options['distance']
            ]);
            $currentThreshold = min($score, $currentThreshold);
        }
    }

    // Reset the best location
    $bestLocation = -1;

    $lastBitArr = [];
    $finalScore = 1;
    $binMax = $patternLen + $textLen;

    $mask = 1 << ($patternLen - 1);

    for ($i = 0; $i < $patternLen; $i++) {
        // Scan for the best match; each iteration allows for one more error.
        // Run a binary search to determine how far from the match location we can stray
        // at this error level.
        $binMin = 0;
        $binMid = $binMax;

        while ($binMin < $binMid) {
            $score = score($pattern, [
                'errors' => $i,
                'currentLocation' => $expectedLocation + $binMid,
                'expectedLocation' => $expectedLocation,
                'distance' => $options['distance']
            ]);

            if ($score <= $currentThreshold) {
                $binMin = $binMid;
            } else {
                $binMax = $binMid;
            }

            $binMid = floor(($binMax - $binMin) / 2 + $binMin);
        }

        // Use the result from this iteration as the maximum for the next.
        $binMax = $binMid;

        $start = max(1, $expectedLocation - $binMid + 1);
        $finish = $options['findAllMatches']
            ? $textLen
            : min($expectedLocation + $binMid, $textLen) + $patternLen;

        // Initialize the bit array
        $bitArr = [];

        $bitArr[$finish + 1] = (1 << $i) - 1;

        for ($j = $finish; $j >= $start; $j -= 1) {
            $currentLocation = $j - 1;

            $offset = mb_substr($text, $currentLocation, 1);
            $charMatch = isset($patternAlphabet[$offset])
                ? $patternAlphabet[$offset]
                : null;

            if ($charMatch) {
                $matchMask[$currentLocation] = 1;
            }

            // First pass: exact match
            $bitArr[$j] = (($bitArr[$j + 1] << 1) | 1) & $charMatch;

            // Subsequent passes: fuzzy match
            if ($i !== 0) {
                $bitArr[$j] |= ((($lastBitArr[$j + 1] | $lastBitArr[$j]) << 1) | 1) | $lastBitArr[$j + 1];
            }

            if ($bitArr[$j] & $mask) {
                $finalScore = score($pattern, [
                    'errors' => $i,
                    'currentLocation' => $currentLocation,
                    'expectedLocation' => $expectedLocation,
                    'distance' => $options['distance']
                ]);

                // This match will almost certainly be better than any existing match.
                // But check anyway.
                if ($finalScore <= $currentThreshold) {
                    // Indeed it is
                    $currentThreshold = $finalScore;
                    $bestLocation = $currentLocation;

                    // Already passed `loc`, downhill from here on in.
                    if ($bestLocation <= $expectedLocation) {
                        break;
                    }

                    // When passing `bestLocation`, don't exceed our current distance from `expectedLocation`.
                    $start = max(1, 2 * $expectedLocation - $bestLocation);
                }
            }
        }

        // No hope for a (better) match at greater error levels.
        $score = score($pattern, [
            'errors' => $i + 1,
            'currentLocation' => $expectedLocation,
            'expectedLocation' => $expectedLocation,
            'distance' => $options['distance']
        ]);

        if ($score > $currentThreshold) {
            break;
        }

        $lastBitArr = $bitArr;
    }

    // Count exact matches (those with a score of 0) to be "almost" exact
    return [
        'isMatch' => $bestLocation >= 0,
        'score' => $finalScore == 0 ? 0.001 : $finalScore,
        'matchedIndices' => matched_indices($matchMask, $options['minMatchCharLength'])
    ];
}