Retrieve the matched length

[Kerollmops]

Hi,

Is there any way/trick to know the length matched by the text used to match on it?

For example when you construct a prefix DFA, try to make it match with a text, the dfa gives you the edit distance but you do not know the exact length that this text "covers" on the original text.

let query = "Levente";
//                ^ missing "sh"

let max_dist = 3;
let dfa = Dfa::new_prefix(query, max_dist);

let text = "Levenshtein";
let dist = dfa.eval(text);
assert_eq!(dist, 2);

Here we can easily retrieve the edit distance but we would also like to know that this text covers 9 characters (i.e. "Levenshte") and not the text length 6 (i.e. "Levente").

Something I though about was to count the number of insertions and deletions, but the DFA doesn't stores that, didn't it?

[Kerollmops]

Hey @fulmicoton,

I just found out that there is a distance method on the DFA that returns the distance associated with this state is there any way to also retrieve the length where the automaton stopped? Is this information stored in the DFA state?

To make it maybe a little more clear, if the original word (hel) that created the DFA is a prefix of another word, is there a way to know where in the targeted word (hello) the DFA stopped (3 chars)? (hello).

Thank you very much!

[fulmicoton]

Hello @Kerollmops ,

where the automaton stopped I am not entirely sure what you mean by "where the automaton stopped".
I assume you are trying to use this to build a highglighter?
There are no such method but if you can contribute one that would be awesome.

[Kerollmops]

Hey @fulmicoton,

where the automaton stopped I am not entirely sure what you mean by "where the automaton stopped".

When I say "where the automaton stopped" I mean "Retrieve the number of bytes consumed by the automaton". In other words being able to know how many bytes have been consumed for this state.

I assume you are trying to use this to build a highglighter?

Exactly, good guess 😀

There are no such method but if you can contribute one that would be awesome.

I understand that there is a Vec of distances and you use the state as an index in this Vec to return the associated distance with the given state.

Do you think it is possible to also create a Vec with the offset in bytes in the original string, when we create the DFA? An offset that indicate where the automaton stoped.

---

I was thinking a little more about this feature and I found out that this is not that easy, what I need is to track the string operations, especially the characters additions and deletions, to reach the targeted string.

I other words being able to know how many characters the original (prefix) string matches on the targeted string. (e.g. if we accept prefixes with one typo, "bld" -> "buldog").

I guess there is multiple ways to reach the same state and therefore there is no way to track the number of characters additions and deletions using the returned state?