Show HN: Subsequential Transducer for Efficient Text Rewriting

Re:Show HN: Subsequential Transducer for Efficient Text Rewr... by binarymax on Wednesday July 05, 2017 @10:16AM (#14702549)

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?

[ Parent | on HN ]

Re:Show HN: Subsequential Transducer for Efficient Text Rewr... by deniskyashif on Wednesday July 05, 2017 @10:24AM (#14702615)

Hi, 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.

[ Parent | on HN ]