|laziness, impatience, and hubris|
Re: Generate unique ids of maximum lengthby rubasov (Friar)
|on Apr 13, 2010 at 20:00 UTC||Need Help??|
Another idea probably worth mentioning: embrace tab completion. Let's suppose we can use tab completion on your input, for instance consider this line:
You must type the marked characters, but the others are optional, they can be completed by pressing tab. Therefore in the shortening process always keep the mandatory characters, but leave out as many optional as needed starting from the right end.
This is achievable by parsing your input into a suffix tree and operating on that.
The first characters of the tree node strings are the mandatory ones, the others are optional. This tree structure seems similar to ikegami's code, however I haven't understood that fully yet, so I'm not sure what's the difference. For me the benefit of this approach seems to be this: you don't need to use the concept of word. Another pro for this algorithm is that you don't need to number your shortened identifiers. (But numbering your input lines (in the base of your input character set) is not bad because that produces the shortest possible unique ids.)
I have some proof of concept code, but take it with a grain of salt: it's unnecessarily complex, employs dirty hacks etc.
Some explanation: I've started by parsing the input into a character-level suffix tree. This tree uses hashes, the keys are the substrings, the values are hashrefs of what can follow. A possible ending position of the string is marked by "" => undef. Then collapsed it to a substring-level suffix tree and descended into that to shorten the ids.
Sorry for the late post, yesterday I haven't got enough time to write this.
p.s.: Am I right this is guaranteed to produce unique ids? I'm not sure, but it seems good.
update: answered my own question: Yes, the uniqueness of the shortened ids is guaranteed, no matter what set of optional characters are left out.