Specifying end of string sentinels in Python prior to constructing a suffix array

Question

I'm implementing algorithms in http://portal.acm.org/citation.cfm?id=1813708 that utilize suffix arrays to find longest common substrings. The algorithms involve constructing a suffix array for a string that is the concatenation of a set of given strings with string separators called sentinels. So for example, if we are given the strings a, b and c, a new string d is created which is a$1b$2c$3 where $1, $2, $3 are the sentinel characters marking the ends of each string. The sentinel characters must be unique and lexicographically less than all other characters in a, b and c.

My question revolves around the representation of the sentinel characters in Python. If a, b and c are ASCII strings, I'm thinking I might need to convert those strings to UTF-8 and shift their range from 0-127 to a higher range such that there are characters available that are lexicographically less than those in the strings. If that seems reasonable, what is the most efficient mechanism for remapping the characters in Python such that their range is N-127+N where N is the number of strings provided?

Answer 1

I think you should use a tokenizer and replace each string with an integer. Then for sentinels, there will be plenty of integers left over. Probably, it's more convenient to use the larger integers as sentinels rather than the small ones. For printout, you can use whatever Unicode character you want, and you may as well use the same character for all of them.

Are you implementing Yamamoto & Church? If so, have a look at some newer literature before you start. I recommend Abouelhoda et al Extended Suffix Array and Kim, Kim & Park, Linearized Suffix Trees. And if you like combinatorics, look at: Schürmann, Klaus-Bernd, Suffix arrays in theory and practice.

Also, I recommend 3-way radix quicksort, as opposed to a specialized suffix sorting algorithm. You only need the suffix sorting algorithm in case of redundancies in your corpus. But these redundancies are unnecessary, and will screw up your statistics.

And if you make something interesting, I would be interested to see

Dale Gerdemann

Answer 2

You can do this using Unicode (not UTF-8) strings. In Python 3, all strings are Unicode but in Python 2, you need the u prefix (ie. "hello" is not Unicode but u"world" is).

>>> s = u"string one"
>>> N = 3
>>> "".join(unichr(ord(x) + N) for x in s)
u'vwulqj#rqh'

For Python 3, this would be slightly simpler:

>>> s = "string one"
>>> N = 3
>>> "".join(chr(ord(x) + N) for x in s)
'vwulqj#rqh'