Comparing strings at grapheme level

moritz has asked for the wisdom of the Perl Monks concerning the following question:

I'm trying to get my head around some Unicode issues:

I want to compare text strings at the grapheme level, and I thought that the way to do it is to use one of the normalization form provided by Unicode::Normalize.

I tried the four most common normalization forms, but different representations of the same grapheme (an "a" with two marking characters in different order) are never converted to the same form.

#!/usr/bin/perl
use strict;
use warnings;
use charnames qw(:full);
use Unicode::Normalize qw(NFKD NFD NFKC NFC reorder);

my $str1 = "\N{LATIN SMALL LETTER A}\N{COMBINING ACUTE ACCENT}\N{COMBI
+NING GRAVE ACCENT}";
my $str2 = "\N{LATIN SMALL LETTER A}\N{COMBINING GRAVE ACCENT}\N{COMBI
+NING ACUTE ACCENT}";
binmode STDOUT, ':utf8';


print "success\n" if $str1 eq $str2;

print "NFKD:\n";
dump_charnames(NFKD($str1));
dump_charnames(NFKD($str2));
print "success\n" if NFKD($str1) eq NFKD($str2);

print "NFD:\n";
dump_charnames(NFD($str1));
dump_charnames(NFD($str2));
print "success\n" if NFD($str1) eq NFD($str2);

print "NFC:\n";
dump_charnames(NFC($str1));
dump_charnames(NFC($str2));
print "success\n" if NFC($str1) eq NFC($str2);

print "NFKC:\n";
dump_charnames(NFKC($str1));
dump_charnames(NFKC($str2));
print "success\n" if NFKC($str1) eq NFKC($str2);

print "reorder:\n";
dump_charnames(reorder($str1));
dump_charnames(reorder($str2));
print "success\n" if reorder($str1) eq reorder($str2);

sub dump_charnames {
    my $str = $_[0];
    print map { '\N{' . charnames::viacode(ord $_) . '}' }
            split m//, $str;
    print "\n";
}
__END__
\N{LATIN SMALL LETTER A}\N{COMBINING ACUTE ACCENT}\N{COMBINING GRAVE A
+CCENT}
\N{LATIN SMALL LETTER A}\N{COMBINING GRAVE ACCENT}\N{COMBINING ACUTE A
+CCENT}
NFD:
\N{LATIN SMALL LETTER A}\N{COMBINING ACUTE ACCENT}\N{COMBINING GRAVE A
+CCENT}
\N{LATIN SMALL LETTER A}\N{COMBINING GRAVE ACCENT}\N{COMBINING ACUTE A
+CCENT}
NFC:
\N{LATIN SMALL LETTER A WITH ACUTE}\N{COMBINING GRAVE ACCENT}
\N{LATIN SMALL LETTER A WITH GRAVE}\N{COMBINING ACUTE ACCENT}
NFKC:
\N{LATIN SMALL LETTER A WITH ACUTE}\N{COMBINING GRAVE ACCENT}
\N{LATIN SMALL LETTER A WITH GRAVE}\N{COMBINING ACUTE ACCENT}
reorder:
\N{LATIN SMALL LETTER A}\N{COMBINING ACUTE ACCENT}\N{COMBINING GRAVE A
+CCENT}
\N{LATIN SMALL LETTER A}\N{COMBINING GRAVE ACCENT}\N{COMBINING ACUTE A
+CCENT}
[download]

What am I doing wrong, and how can I transform the strings to a canonical form that is fit for comparison?

Or is it just this weird grapheme which doesn't occur "in the wild" and causes problems?

Comment on Comparing strings at grapheme level Download Code

Replies are listed 'Best First'.
Re: Comparing strings at grapheme level by halley (Prior) on Jan 09, 2008 at 14:51 UTC
I just did a google search and it looks like this is fairly authoritative, but still not quite helpful in your situation. http://unicode.org/reports/tr15/#Stability_of_Normalized_Forms http://unicode.org/reports/tr15/#Canonical_Equivalence It would seem that if the normalization functions worked to that spec, then they would always produce the same output order. However, in my limited experience I've never seen any real-world cases where you'd want or need multiple COMBINING characters... not saying it doesn't exist but the Unicode docs don't obviously mention it specifically. I would say that if you're straying outside the defined normalization routines, that you gotta do something stable and predictable, like sort your multiple COMBINING elements into numerical codepoint order. (Order of these should never matter for the grapheme, right?) Update: http://useless-factor.blogspot.com/2007/07/unicode-implementers-guide-part-2.html This blog says ordering does matter, and that they should be sorted by class of combining element. The ordering of combining elements in the same class may or may not need to be maintained, which is the issue you're running into. Pretty annoying if there's not a standard library implementation of all this. My perlish hat says that to compare two graphemes, you'd have to do a hash/set of included characters, then compare the hashes for equivalence. If those match, and the order of combining classes is the same, it's the same grapheme. -- `[ e d @ h a l l e y . c c ]`	[reply]
Re^2: Comparing strings at grapheme level by moritz (Cardinal) on Jan 10, 2008 at 10:02 UTC
Thanks for your helpful post. At the moment I have no real Unicode problems (but I rather try to understand the concepts). I'll keep that in mind when I start do some real work with Unicode.	[reply]


No such thing as a small change
	PerlMonks