src/modules/launcher/Wox.Infrastructure/StringMatcher.cs
/// <summary>
/// Current method:
/// Character matching + substring matching;
/// 1. Query search string is split into substrings, separator is whitespace.
/// 2. Check each query substring's characters against full compare string,
/// 3. if a character in the substring is matched, loop back to verify the previous character.
/// 4. If previous character also matches, and is the start of the substring, update list.
/// 5. Once the previous character is verified, move on to the next character in the query substring.
/// 6. Move onto the next substring's characters until all substrings are checked.
/// 7. Consider success and move onto scoring if every char or substring without whitespaces matched
/// </summary>
Current method:
Character matching + substring matching;
1. Query search string is split into substrings, separator is whitespace.
2. Check each query substring's characters against full compare string,
3. if a character in the substring is matched, loop back to verify the previous character.
4. If previous character also matches, and is the start of the substring, update list.
5. Once the previous character is verified, move on to the next character in the query substring.
6. Move onto the next substring's characters until all substrings are checked.
7. Consider success and move onto scoring if every char or substring without whitespaces matched
Current method : Character matching + substring matching ; 1 . Query search string is split into substrings separator is whitespace . 2 . Check each query substring ' s characters against full compare string 3 . if a character in the substring is matched loop back to verify the previous character . 4 . If previous character also matches and is the start of the substring update list . 5 . Once the previous character is verified move on to the next character in the query substring . 6 . Move onto the next substring ' s characters until all substrings are checked . 7 . Consider success and move onto scoring if every char or substring without whitespaces matched
public MatchResult FuzzyMatch(string query, string stringToCompare, MatchOption opt)
        {
            if (string.IsNullOrEmpty(stringToCompare) || string.IsNullOrEmpty(query)) return new MatchResult (false, UserSettingSearchPrecision);
            query = query.Trim();
            if (_alphabet != null)
            {
                query = _alphabet.Translate(query);
                stringToCompare = _alphabet.Translate(stringToCompare);
            }
            var fullStringToCompareWithoutCase = opt.IgnoreCase ? stringToCompare.ToLower() : stringToCompare;
            var queryWithoutCase = opt.IgnoreCase ? query.ToLower() : query;
            var querySubstrings = queryWithoutCase.Split(new[] { ' ' }, StringSplitOptions.RemoveEmptyEntries);
            int currentQuerySubstringIndex = 0;
            var currentQuerySubstring = querySubstrings[currentQuerySubstringIndex];
            var currentQuerySubstringCharacterIndex = 0;
            var firstMatchIndex = -1;
            var firstMatchIndexInWord = -1;
            var lastMatchIndex = 0;
            bool allQuerySubstringsMatched = false;
            bool matchFoundInPreviousLoop = false;
            bool allSubstringsContainedInCompareString = true;
            var indexList = new List<int>();
            List<int> spaceIndices = new List<int>();
            for (var compareStringIndex = 0; compareStringIndex < fullStringToCompareWithoutCase.Length; compareStringIndex++)
            {
                if (fullStringToCompareWithoutCase[compareStringIndex].Equals(' ') && currentQuerySubstringIndex == 0)
                {
                    spaceIndices.Add(compareStringIndex);
                }
                if (fullStringToCompareWithoutCase[compareStringIndex] != currentQuerySubstring[currentQuerySubstringCharacterIndex])
                {
                    matchFoundInPreviousLoop = false;
                    continue;
                }
                if (firstMatchIndex < 0)
                {
                    firstMatchIndex = compareStringIndex;
                }
                if (currentQuerySubstringCharacterIndex == 0)
                {
                    matchFoundInPreviousLoop = true;
                    firstMatchIndexInWord = compareStringIndex;
                }
                else if (!matchFoundInPreviousLoop)
                {
                    var startIndexToVerify = compareStringIndex - currentQuerySubstringCharacterIndex;
                    if (AllPreviousCharsMatched(startIndexToVerify, currentQuerySubstringCharacterIndex, fullStringToCompareWithoutCase, currentQuerySubstring))
                    {
                        matchFoundInPreviousLoop = true;
                        firstMatchIndex = currentQuerySubstringIndex == 0 ? startIndexToVerify : firstMatchIndex;
                        indexList = GetUpdatedIndexList(startIndexToVerify, currentQuerySubstringCharacterIndex, firstMatchIndexInWord, indexList);
                    }
                }
                lastMatchIndex = compareStringIndex + 1;
                indexList.Add(compareStringIndex);
                currentQuerySubstringCharacterIndex++;
                if (currentQuerySubstringCharacterIndex == currentQuerySubstring.Length)
                {
                    allSubstringsContainedInCompareString = matchFoundInPreviousLoop && allSubstringsContainedInCompareString;
                    currentQuerySubstringIndex++;
                    allQuerySubstringsMatched = AllQuerySubstringsMatched(currentQuerySubstringIndex, querySubstrings.Length);
                    if (allQuerySubstringsMatched)
                        break;
                    currentQuerySubstring = querySubstrings[currentQuerySubstringIndex];
                    currentQuerySubstringCharacterIndex = 0;
                }
            }
            if (allQuerySubstringsMatched)
            {
                var nearestSpaceIndex = CalculateClosestSpaceIndex(spaceIndices, firstMatchIndex);
                var score = CalculateSearchScore(query, stringToCompare, firstMatchIndex - nearestSpaceIndex - 1, lastMatchIndex - firstMatchIndex, allSubstringsContainedInCompareString);
                return new MatchResult(true, UserSettingSearchPrecision, indexList, score);
            }
            return new MatchResult (false, UserSettingSearchPrecision);
        }
public MatchResult FuzzyMatch ( string query , string stringToCompare , MatchOption opt ) { if ( string . IsNullOrEmpty ( stringToCompare ) || string . IsNullOrEmpty ( query ) ) return new MatchResult ( false , UserSettingSearchPrecision ) ; query = query . Trim ( ) ; if ( _alphabet != null ) { query = _alphabet . Translate ( query ) ; stringToCompare = _alphabet . Translate ( stringToCompare ) ; } var fullStringToCompareWithoutCase = opt . IgnoreCase ? stringToCompare . ToLower ( ) : stringToCompare ; var queryWithoutCase = opt . IgnoreCase ? query . ToLower ( ) : query ; var querySubstrings = queryWithoutCase . Split ( new [ ] { ' ' } , StringSplitOptions . RemoveEmptyEntries ) ; int currentQuerySubstringIndex = 0 ; var currentQuerySubstring = querySubstrings [ currentQuerySubstringIndex ] ; var currentQuerySubstringCharacterIndex = 0 ; var firstMatchIndex = - 1 ; var firstMatchIndexInWord = - 1 ; var lastMatchIndex = 0 ; bool allQuerySubstringsMatched = false ; bool matchFoundInPreviousLoop = false ; bool allSubstringsContainedInCompareString = true ; var indexList = new List < int > ( ) ; List < int > spaceIndices = new List < int > ( ) ; for ( var compareStringIndex = 0 ; compareStringIndex < fullStringToCompareWithoutCase . Length ; compareStringIndex ++ ) { if ( fullStringToCompareWithoutCase [ compareStringIndex ] . Equals ( ' ' ) && currentQuerySubstringIndex == 0 ) { spaceIndices . Add ( compareStringIndex ) ; } if ( fullStringToCompareWithoutCase [ compareStringIndex ] != currentQuerySubstring [ currentQuerySubstringCharacterIndex ] ) { matchFoundInPreviousLoop = false ; continue ; } if ( firstMatchIndex < 0 ) { firstMatchIndex = compareStringIndex ; } if ( currentQuerySubstringCharacterIndex == 0 ) { matchFoundInPreviousLoop = true ; firstMatchIndexInWord = compareStringIndex ; } else if ( ! matchFoundInPreviousLoop ) { var startIndexToVerify = compareStringIndex - currentQuerySubstringCharacterIndex ; if ( AllPreviousCharsMatched ( startIndexToVerify , currentQuerySubstringCharacterIndex , fullStringToCompareWithoutCase , currentQuerySubstring ) ) { matchFoundInPreviousLoop = true ; firstMatchIndex = currentQuerySubstringIndex == 0 ? startIndexToVerify : firstMatchIndex ; indexList = GetUpdatedIndexList ( startIndexToVerify , currentQuerySubstringCharacterIndex , firstMatchIndexInWord , indexList ) ; } } lastMatchIndex = compareStringIndex + 1 ; indexList . Add ( compareStringIndex ) ; currentQuerySubstringCharacterIndex ++ ; if ( currentQuerySubstringCharacterIndex == currentQuerySubstring . Length ) { allSubstringsContainedInCompareString = matchFoundInPreviousLoop && allSubstringsContainedInCompareString ; currentQuerySubstringIndex ++ ; allQuerySubstringsMatched = AllQuerySubstringsMatched ( currentQuerySubstringIndex , querySubstrings . Length ) ; if ( allQuerySubstringsMatched ) break ; currentQuerySubstring = querySubstrings [ currentQuerySubstringIndex ] ; currentQuerySubstringCharacterIndex = 0 ; } } if ( allQuerySubstringsMatched ) { var nearestSpaceIndex = CalculateClosestSpaceIndex ( spaceIndices , firstMatchIndex ) ; var score = CalculateSearchScore ( query , stringToCompare , firstMatchIndex - nearestSpaceIndex - 1 , lastMatchIndex - firstMatchIndex , allSubstringsContainedInCompareString ) ; return new MatchResult ( true , UserSettingSearchPrecision , indexList , score ) ; } return new MatchResult ( false , UserSettingSearchPrecision ) ; }
Current method:
Character matching + substring matching;
1.
Current method : Character matching + substring matching ; 1 .
// To maintain a list of indices which correspond to spaces in the string to compare // To populate the list only for the first query substring // first matched char will become the start of the compared string // first letter of current word // we want to verify that there is not a better match if this is not a full word // in order to do so we need to verify all previous chars are part of the pattern // if it's the beginning character of the first query substring that is matched then we need to update start index // if finished looping through every character in the current substring // if any of the substrings was not matched then consider as all are not matched // otherwise move to the next query substring // proceed to calculate score if every char or substring without whitespaces matched
query
string
stringToCompare
string
opt
MatchOption