-
June 23rd, 2013, 02:31 PM
#1
Can someone explain me how does the common_prefix function work?
t's about a cpp implementation of acyclic FSA, the algorithm from Daciuk & Watson. http://acl.ldc.upenn.edu/J/J00/J00-1002.pdf
Here a part of the algorithm:
Register := empty;
do there is another word ->
Word := next word in lexicographic order;
CommonPrefix := common_prefix(Word);
LastS tate := delta*(q0, CommonPrefix ) ;
CurrentSuffix := Word[length(CommonPrefix)+ l. ... length(Word)l;
if has_children(LastState) ->
replace_or_register(LastState)
fi;
add_suffix(LastState, CurrentSuffix)
od;
replace_or_register(qo)
func common_prefix(Word) ->
return the longest prefix w of Word such that delta*(q0, w) is not undefined
....
Can someone explain me how does the common_prefix function work? Maybe with a simple example?
They say: The function common_prefix finds the longest prefix (of the word to be added) that is a prefix of a word already in the automaton. The prefix can be empty. But I don't get it.
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|