Struct fuzzy_matcher::skim::SkimMatcherV2

pub struct SkimMatcherV2 { /* fields omitted */ }

Fuzzy matching is a sub problem is sequence alignment. Specifically what we'd like to implement is sequence alignment with affine gap penalty. Ref: https://www.cs.cmu.edu/~ckingsf/bioinfo-lectures/gaps.pdf

Given pattern(i) and choice(j), we'll maintain 2 score matrix:

M[i][j] = match(i, j) + max(M[i-1][j-1] + consecutive, P[i-1][j-1])
M[i][j] = -infinity if p[i][j] do not match

M[i][j] means the score of best alignment of p[..=i] and c[..=j] ending with match/mismatch e.g.:

c: [.........]b
p: [.........]b

So that p[..=i-1] and c[..=j-1] could be any alignment

P[i][j] = max(M[i][j-k]-gap(k)) for k in 1..j

P[i][j] means the score of best alignment of p[..=i] and c[..=j] where c[j] is not matched.
So that we need to search through all the previous matches, and calculate the gap.

  (j-k)--.   j
c: [....]bcdef
p: [....]b----
         i

Note that the above is O(n^3) in the worst case. However the above algorithm uses a general gap penalty, but we use affine gap: gap = gap_start + k * gap_extend where:

• u: the cost of starting of gap
• v: the cost of extending a gap by one more space.

So that we could optimize the algorithm by:

P[i][j] = max(gap_start + gap_extend + M[i][j-1], gap_extend + P[i][j-1])

Besides, since we are doing fuzzy matching, we'll prefer some pattern over others. So we'll calculate in-place bonus for each character. e.g. bonus for camel cases.

In summary:

B[j] = in_place_bonus_of(j)
M[i][j] = match(i, j) + max(M[i-1][j-1] + consecutive, P[i-1][j-1])
M[i][j] = -infinity if p[i] and c[j] do not match
P[i][j] = max(gap_start + gap_extend + M[i][j-1], gap_extend + P[i][j-1])

Implementations

impl SkimMatcherV2

pub fn score_config(self, score_config: SkimScoreConfig) -> Self

pub fn element_limit(self, elements: usize) -> Self

pub fn ignore_case(self) -> Self

pub fn smart_case(self) -> Self

pub fn respect_case(self) -> Self

pub fn use_cache(self, use_cache: bool) -> Self

pub fn debug(self, debug: bool) -> Self

pub fn fuzzy(
    &self,
    choice: &str,
    pattern: &str,
    with_pos: bool
) -> Option<(i64, Vec<usize>)>

pub fn simple_match(
    &self,
    choice: &[char],
    pattern: &[char],
    first_match_indices: &[usize],
    case_sensitive: bool,
    with_pos: bool
) -> Option<(i64, Vec<usize>)>

Trait Implementations

impl Default for SkimMatcherV2

fn default() -> Self

Returns the "default value" for a type.

impl FuzzyMatcher for SkimMatcherV2

fn fuzzy_indices(
    &self,
    choice: &str,
    pattern: &str
) -> Option<(i64, Vec<usize>)>

fuzzy match choice with pattern, and return the score & matched indices of characters

fn fuzzy_match(&self, choice: &str, pattern: &str) -> Option<i64>

fuzzy match choice with pattern, and return the score of matching