[−][src]Struct fuzzy_matcher::skim::SkimMatcherV2
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
[src]
pub fn score_config(self, score_config: SkimScoreConfig) -> Self
[src]
pub fn element_limit(self, elements: usize) -> Self
[src]
pub fn ignore_case(self) -> Self
[src]
pub fn smart_case(self) -> Self
[src]
pub fn respect_case(self) -> Self
[src]
pub fn use_cache(self, use_cache: bool) -> Self
[src]
pub fn debug(self, debug: bool) -> Self
[src]
pub fn fuzzy(
&self,
choice: &str,
pattern: &str,
with_pos: bool
) -> Option<(i64, Vec<usize>)>
[src]
&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>)>
[src]
&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
[src]
impl FuzzyMatcher for SkimMatcherV2
[src]
Auto Trait Implementations
impl !RefUnwindSafe for SkimMatcherV2
impl Send for SkimMatcherV2
impl Sync for SkimMatcherV2
impl Unpin for SkimMatcherV2
impl UnwindSafe for SkimMatcherV2
Blanket Implementations
impl<T> Any for T where
T: 'static + ?Sized,
[src]
T: 'static + ?Sized,
impl<T> Borrow<T> for T where
T: ?Sized,
[src]
T: ?Sized,
impl<T> BorrowMut<T> for T where
T: ?Sized,
[src]
T: ?Sized,
fn borrow_mut(&mut self) -> &mut T
[src]
impl<T> From<T> for T
[src]
impl<T, U> Into<U> for T where
U: From<T>,
[src]
U: From<T>,
impl<T, U> TryFrom<U> for T where
U: Into<T>,
[src]
U: Into<T>,
type Error = Infallible
The type returned in the event of a conversion error.
fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>
[src]
impl<T, U> TryInto<U> for T where
U: TryFrom<T>,
[src]
U: TryFrom<T>,