Once more into the palindrome

by Michael S. Kaplan, published on 2005/06/15 05:21 -04:00, original URI: http://blogs.msdn.com/b/michkap/archive/2005/06/15/429279.aspx

Back in April, in a series of posts, I talked about many cool features in Whidbey, from comparison (been there all along) to text elements (been there all along, better in Whidbey) to normalization (new in Whidbey), all in the context of one of the most important features that any computer program can possibly support -- palindrome detection:

Looking for that internationally savvy palindrome checker....
Where did the new StringInfo stuff come from?
Normalization vs. .NET text elements

It was all very cool stuff, and a lot of fun to do.

And then I blew it.

In that last post, I said:

Now, Maurits went on in his Channel 9 posting to discuss sort elements, or cases when two or more characters are to be given a single sort weight (kind of the opposite of an expansion like these ligatures). However, in my opinion these are not really suitable for a palindrome detection algorithm, as I don't think they are usually treated as letters except in the case where they are also treated as unique text elements (the case covered by the StringInfo code).

Any native speakers of languages with such constructs as the Spanish ch and the Hungarian dzs who think they should or should not be treated as a unit in trying to detect palindomosity should feel free to leave a comment to that effect. Also, if any of my collagues in the GIFT group agree or disagree here (and they are reading this!) they are invited to do the same (or stop me in the hall and accost me with this information!).

Well, the good news is that no one accosted me.

The bad news is that some people posted that I was wrong, and colleagues informed me that I was wrong. Those 'sort elements' (for lack of a better term) would be taken as a unit, just as the text elements are.

Damn. I hate being wrong.

Especially when I pointed out that there was no good way pick up these 'sort element' compressions, where two or more UTF-16 code points are given the weight of a single element. We have the data, sure. But we do not currently excpose it in a convenient way to answer this particular question.

And to top it all off, there is no good way to reverse a sort key, though the sort key obviously contains the information about when these compressions (known in the Unicode Collation Algorithm as 'contractions').

I stewed on this for a bit today, after finally deciding to tackle this post. There had to be some way short of a new Win32 or .NET function to make this work.

So I closed my eyes and told myself to pretend I was interviewing for a job at Microsoft. :-)

Then something suddenly occurred to me!

We do not care about reversing or undoing the sort key; we only care about comparing the pieces of each sort key! And we can do that, we have the bytes, so why not just compare them?

Let's take a hideously contrived string to test for palindromodity: abddzsCÅbÅCdzsdzsba

The code points are:

0061 0062 0064 0064 007a 0073 0043 00c5 0062 0041 030a 0043 0064 007a 0073 0064 007a 0073 0062 0061

Note especially the Hungarian dzs double compression ('ddzs' == 'dzsdzs') and the A Ring in both precomposed and composite forms (code points marked in bold).

We grab the sort key:

string st = "abddzsCÅbÅCdzsdzsba";
CompareInfo ci = CompareInfo.GetCompareInfo("hu-HU");
byte[] rgbyt = ci.GetSortKey(stIn, CompareOptions.None).KeyData

and then take a look at what those bytes look like:

0e 02 0e 09 0e 1e 0e 1e 0e 0a 0e 02 0e 09 0e 02 0e 0a 0e 1e 0e 1e 0e 09 0e 02 01 02 02 02 02 02 1a 02 1a 01 02 02 02 02 12 12 02 12 12 01 01 00

Let's split it into the various pieces: 

UW: 0e 02 0e 09 0e 1e 0e 1e 0e 0a 0e 02 0e 09 0e 02 0e 0a 0e 1e 0e 1e 0e 09 0e 02 01
DW: 02 02 02 02 02 1a 02 1a 01
CW: 02 02 02 02 12 12 02 12 12 01
SW: 01 00

Now the rules are very simple for the detection:

1. Strip out the 00 and 01 byte values, those are just sentinels;
2. The UW values will always be two bytes per sort element, and will always therefore be an even number;
3. The DW/CW/SW weights can be prefixed by 02 byte values. You can ignore them, and assume that identical weights exist in suffix form if the weight ends early (02 is the minimal weight and is just used to pad the piece of the sort key when are looking further into the string).

So, looking at our sort key:

Yes folks, we have a palindrome! And the method to do so is using code that has been around since NT 3.1.

Now if you really want to, you can normalize the string to take care of some of the issues brought up in the earlier posts.

The code to sort through the byte array and verify the results is left as an exercise for the reader. If someone had figured this out in an interview, they would have impressed the hell out of me; I am temporarily way too impressed with myself for thinking of it.... :-)

I will do some more "sort key cracking" another day, if there is interest. I have only ever known on one team inside or outside of Microsoft that has ever had a scenario that required cracking sort keys, but perhaps I have just not talked to everyone yet. I have run across many people who have found it to be an interesting area, even if they could not find an immediate use for the knowledge.

This post brought to you by "﴿" (U+fd3f, a.k.a. ORNATE RIGHT PARENTHESIS)

# Atsushi Enomoto on 15 Jun 2005 9:01 AM:

# Michael S. Kaplan on 15 Jun 2005 10:09 AM:

# serras on 15 Jun 2005 2:55 PM:

# Michael S. Kaplan on 15 Jun 2005 3:45 PM:

# Ruben on 15 Jun 2005 4:58 PM:

# Maurits [MSFT] on 15 Jun 2005 6:43 PM:

# Maurits [MSFT] on 15 Jun 2005 6:46 PM:

# Maurits [MSFT] on 15 Jun 2005 7:09 PM:

# Michael S. Kaplan on 15 Jun 2005 7:48 PM:

# Michael S. Kaplan on 15 Jun 2005 10:53 PM:

# Maurits [MSFT] on 17 Jun 2005 4:41 PM:

# Ruben on 17 Jun 2005 5:37 PM:

# Michael S. Kaplan on 17 Jun 2005 8:47 PM:

# Michael S. Kaplan on 17 Jun 2005 8:49 PM:

referenced by

go to newer or older post, or back to index or month or day