Documentation

The constant environment in which the search runs.

Type synonym for the index of a candidate in the backing vector along with the positions of the matches for it.

The configuration for a search style with n needles and matcher of type a

The full match consisting of a score for the match and vector consisting of the positions of the match. The score is intended as for bucketing and as a result shouldn't be two large and must be non-negative . For the fuzzy style in this module n contiguous matches contribute n-1 to the score. The scores thus range from 0 to n-1 where n is the length of the string to be matched. For orderless style this score is always 0.

The matching process essentially takes the form of a fold with possible early termination over the matches produced. See the runLower from the alfred-margaret. Here MatchState is the return type of this fold and essentially it records the positions of the matches. Here like in alfred-margaret position is the code unit index of the first code unit beyond the match. We can't use the CodeUnitIndex here because it doesn't have an unbox instance.

The existential version of MatcherSized

The MatcherSized type consists of a state machine for matching a fixed number of needles. The number of matches needed is encoded in the Nat parameterzing the type. Here the purpose is to improve the memory consumption by utlizing the Unbox instance for sized tagged unboxed vectors from (vector-sized)[https:/hackage.haskell.orgpackage/vector-sized] package. This significantly reduces the memory consumption. At least in the present implementation there is no benefit for correctness and dealing with the length tag is occasionally annoying.

Constructs the matcher for fuzzy matching. The needles are all possible contigous subtrings of the string being matched. The Nat n must be instantiated at the length n of the query string. They are n choose 2 such substrings, so to the complexity of matching is \(O(m + n^2)\) where m is the length of candidate string. This is a rough (and probably wrong) estimate as the updating the matchstate for each found match is not a constant time operation. Not sure if Aho Corasick is the optimal way for this kind of matching but in practice it seems fast enough.

Unsized version of fuzzyMatcherSized

Constructs the matcher for orderless matching, the needles are the words from the query string and the proxy argument should be instantiated at the number of words.

Unsized version of orderlessMatcherSized

The parts of a string resulting from a match using the fuzzy matcher.

The parts of a string resulting from a match using the orderless matcher. See parts for an explanation of arguments.

Shorten a match by collapsing the contiguous sub-matches together.

Search functions suitable for fuzzy matching. The candidate c will match query s if c contains all the characters in s in order. In general there can be several ways of matching. This tries to find a match with minimum number of parts of. It does not find the minimum number of parts, if that requires reducing the extent of the partial match during search. E.g. matching "as" against "talash" the split will be ["tal","as","h"] and not ["t","a","la","s","h"]. While matching "talash best match testing hat" against "tea" will not result in ["talash best match ","te","sting h","a","t"] since "te" occurs only after we have match all three letters and we can't know if we will find the "a" without going through the string.

Search functions that match the words in i.e. space separated substring in any order. "talash best" will match "be as" with the split ["tal","as","h","be","st"] but "talash best" will not match "bet".