4 ms·
Interesting project. Question on this: "For any text t of length |t| the time it takes to perform a rewrite is O(|t|+|t'|) where t' denotes the resulting outpu
by binarymax 9y ago
Interesting project. Question on this: "For any text t of length |t| the time it takes to perform a rewrite is O(|t|+|t'|) where t' denotes the resulting output string"
Wouldn't the vocabulary size fit into the order complexity? Vocabs that would be considered useful in this context tend to be quite large. Are you achieving worst case logn of search in the vocab?
- deniskyashif 9y agoHi, thanks! The outputs are encoded in the transitions and the states themselves, so the vocabulary size doesn't affect the search. It affects, however, the construction because for each node in the trie we have to add an outgoing transition for each distinct symbol of the input vocabulary.