From: hiraga@Csli.Stanford.EDU (Yuzuru Hiraga)
Subject: Re: Sorting japanese strings
Organization: Stanford University CSLI
Date: Sat, 10 Oct 1992 09:17:08 GMT

In article <BvuIB4.3Ku@iai.kfk.de> harry@issun1.kfk.de writes:
>I spent some time developing an algorithm for sorting
>japanese strings in the order the appear in a usual dictionary. It works,
>but I am not very satiesfied with it, because it is not very straightforward.
>
>My question: Is there somewhere a standard algorithmn for sorting japanese strings
>(There must be at least one, I am very sure) in dictionary order.
>To make the point clear: I don't mean strings only composed of kana, I mean strings
>containing the usual mixture of kanji and kana.


First of all, let's consider kana-only strings.
Simply sorting by JIS-code order won't do, so some hacking is necessary
(and I guess you already know that).

The situation is similar to sorting strings with upper-case and lower-case
letters mixed in it, though a bit more complex.
The upper/lower-case mixture is directly analogous to the mixture of
hiragana and katakana.  First, normalize them to a single case --
either all-hiragana or all-katakana, or perhaps more preferrably,
to your own internal code.
As for homonyms, you further need a precedence order between
hiragana and katakana.  Hiragana usually comes first, so for example,
with "anpu" (hiragana: to memorize a score) and "ANPU" (katakana:
< amp = amplifier), the former comes first.

Similar considerations are necessary for kana with DAKUON (voiced sound,
as with ka<->da, ha<->ba<->pa), as well as YOUON (contracted sound, as in
the small "yo" in "kyou") and SOKUON (assimilated sound, the small "tsu"
in "itta").  Taking the case of DAKUON, make sure that "hakata" precedes
"hagata", but not "hagaki" -- i.e. hagaki < hakata < hagata.
This can be directly implemented in code, but the following is a "smart"
way to do it:
* Separate the dakuon and han-dakuon from the base kana character,
  and assign them some numerical code: eg. 0 for no dakuon, 1 for dakuon,
  and 2 for han-dakuon.  Eg.
	paka   -> ha2ka0	(not a real word: used only for illustration)
	hagaki -> ha0ka1ki0
	hakata -> ha0ka0ta0
	hagata -> ha0ka1ta0
* Move the numerical code to the end, eg.
	ha2ka0    -> haka20
	ha0ka1ki0 -> hakaki010
	ha0ka0ta0 -> hakata000
	ha0ka1ta0 -> hakata010
* Sort the result mechanically by lexicographical ordering,
  assuming an extended AIUEO ordering of
	0 < 1 < 2 < ... < a < i < u < e < o < ka < ki < ... < wa < wo < n.

Check that it works.
YOUON's and SOKUON can be treated similarly, although it's not clear
whether this method will be more efficient than direct coding.

The coding so far will be a nice exercise problem for
an introductory/intermediate level programming course,
and I have actually tried that out.


Next, strings including kanji.
The basic idea is to provide a kana reading of the kanji part.
It is recommended to separate the kana-sorter and the kana-reading supplier,
in order to gain more flexibility.  The treatment of kanji homonyms
then remains a problem, and there seems to be no well-defined ordering
for them (which of course, in turn, means that you can provide any
ordering you like, eg. in JIS-code order).
The most practical solution is to provide the kana reading manually.
And if you're working with a dictionary, this may be readily available.

But if you're going to do it automatically, then you're in trouble.
The basic method is to look-up a kana-kanji dictionary.
A straightforward look-up (taking the maximally matched string is a good bet)
will take care of the majority of cases, but will also fail abruptly
in many cases as well (I can give you some good examples, but will be
omitted here because it'll be difficult to explain without using
Japanese character code).
In order to refine on it, it is in effect necessary to do some
morphological analysis, but that's still not enough -- further analysis
eg. syntactical analysis, and even contextual/pragmatic analysis
is necessary.  In short, a full understanding of the string is
necessary to come up with a correct kanji->kana conversion.
This will well constitute a full research project.
Note that kana->kanji conversion methods are assessed as a major
achievement in Japanese AI research (by a field study committee
from the United States).

Hope this helps.

-Yuzuru Hiraga (hiraga@csli.stanford.edu)
Newsgroups: sci.lang.japan