This module provides approximate string matching procedures loosely based on Sublime Text’s approach.
In the context of this collection, the following terms apply:
haystack: A string that may contain needles.
scoring procedure: A procedure that returns a score.
|(require fuzzy-search)||package: fuzzy-search|
(fuzzy-search needle haystack [ assign-score #:max-match-count max-match-count #:max-depth max-depth #:case-sensitive? case-sensitive?])
(hash/c exact-nonnegative-integer? exact-nonnegative-integer? #:immutable #t) needle : string? haystack : string? assign-score : score/c = forrest-skinner max-match-count : exact-positive-integer? = 256 max-depth : exact-positive-integer? = 10 case-sensitive? : any/c = #f
#t if a match was found.
The search will record a match for every contiguous character in needle found in haystack. If the number of matches exceeds max-match-count, then the search will conclude as if no match occurred, and with a score of 0.
Recursive searches in substrings of haystack will commence in order to find higher scoring matches. max-depth limits the recursion depth of the search. While searches are themselves called in tail position, max-depth can still help reduce the runtime of the search.
When case-sensitive? is #f, characters from the needle and haystack are first normalized with char-downcase before being compared.
(-> (hash/c exact-nonnegative-integer? exact-nonnegative-integer? #:immutable #t) string? exact-positive-integer? exact-positive-integer? exact-integer?)
This procedure accepts the following arguments, in order:
The length of the haystack.
The number of matches found in the haystack.
(define score/forrest (score/all (λ _ 100) (score/all/leading-letter -5 -15) (score/all/unmatched-letter -1) (score/match (score/match/sequence 15) (score/match/first-letter 15) (score/match/pair (score/pair/camel-case 30) (score/pair/prefixed 30 '(#\space #\_))))))
(score-if t v)
Useful for combining several score/c procedures.
v : exact-integer? limit : exact-positive-integer?
Use to base a penalty or reward on how far the first match is from the beginning of its haystack.
The returned procedure is also meant for use in score/match.
That procedure returns a score of v if a given pair of characters changes from lowercase to uppercase. It returns a score of 0 otherwise.
That procedure returns a score of v if the first of a given pair of characters appears in chars. It returns a score of 0 otherwise.
|(require fuzzy-search/require)||package: fuzzy-search|
(fuzzy needle ...)
The filesystem search entails use of find-files starting from the directory of the module using fuzzy, or (current-directory) if the source directory is unknown. Paths relative to the file using fuzzy are then treated as haystacks for fuzzy-search.
This is useful if you are prototyping a Racket package and are likely to shuffle files around. Normally when you move a file, all relative path require subforms will break. fuzzy forms may break. A break would occur if a needle targeting a file becomes ambiguous, or if the intended file moves out of the search scope.
The implementation is based on Forrest Smith’s work with Sublime Text’s fuzzy search. That link will take you to his content and public domain source code. Thanks, Forrest!
You can find the source code of this package here.
My own contributions are as follows:
Refactor the code to allow scoring procedures and combinators as part of the public API.
Make case-sensitivity an option.
Expose match positions in program output.
Package for distribution on the Racket catalog.
Add the fuzzy require subform.
If you found my additions useful, then please consider sponsoring my work. I count on your support to continue writing libraries like this one.