🚀 go-pugleaf

Sorting algorithm for "foreign" character set.
Except for asiatic character sets which use 2-byte codes, all characters
are 1 byte.  Thus, to sort you can either

Replace all accented letters with the corresponding non-accented letter.
For example, it is acceptable to have e' = e` = e^ = e" = e so that
the mapping is done only for accented letters.

Or you can do this : replace all letters (i.e. <alt-1> to <alt-255> using
a table to their corresponding position.  The table index is the input
character and each table position is the output character.
Table could look like :
table ['a'] = 'a'
table ['b'] = 'd'
table ['c'] = 'e'
table ['d'] = 'g'
etc.
table ['a`']= 'b'
table ['a^']= 'c'
table ['c,']= 'f'

In other words, all characters are moved to let place for the accented letters.
And this includes standard English letters.


Two last points : I personnaly use the first model, i.e. I check for higher
bit and if 1, I then replace the accented by not accented letters.  Drawbacks
for my own use of sort : I has some accented and non-accented names in the
same file.  I can get in a few cases : Ade`le Adele Ade`le but since I have
usually more data on the sorted line, I just don't care about that.

Second : there are 2 places where to embed the re-coding mechanism :
when getting a line, recode it and sort by using the recoded version, but
using a structure so that the recoded line and the original line are moved
together while sorting.  Other mechanism consists in checking for accented
letters while sorting (in the compare function).  I use the second mechanism
because it needs less space in memory.


Previous articles follow.

In article <1992Sep21.113408.3055@cbnewsj.cb.att.com> davet@cbnewsj.cb.att.com (Dave Tutelman) writes:
>In article <Buvo30.GvL@ireq.hydro.qc.ca> beaurega@ireq.hydro.qc.ca (Denis Beauregard) writes:
>>In article <22226@optima.cs.arizona.edu> robert@cs.arizona.edu (Robert J. Drabek) writes:
>>>Denis Beauregard writes:
>>>> [IN FRENCH] The accented letters are sorted by
>>>> a a` b c c, d e e' e` e^ e" f g h i i^ j k l m n o o^ p q r s t u u` u^ u"
>>>> v w x y z
>>  ...
>>>Are you saying sorting is as below? (not real words, of course)
>>>   meno,  mepo,  meqo,  me'no,  me'po,  me'qo,  me`no,  me`po,  me`qo  [1]
>
>>No, like this:
>>    meno, me'no, me`no, mepo, me'po, me`po, meqo, me'qo, me`qo   [2]
>
>This presents a REAL problem, as follows:
>
>The sorted sequence Bob shows  [1] is the result of taking Denis' collating
>sequence and doing a standard string sort using it. 
>(By standard string sort, I mean that the character on the left is a more
>significant place in the sort than the character on the right.)
>
>To give the sorted sequence that Denis shows [2] requires not only his
>collating sequence, but a new algorithm.  It also requires a more complex
>alphabet, in that:
> - As Denis points out, e' and e^ and e" are all SINGLE symbols, but...
> - All the "e" symbols must be deemed "equal" in some sense, when sorting.
>   That is, the sort must be done FIRST with all the "e" symbols treated
>   the same, then an internal sort done using the collating sequence.
>Therefore, the alphabet not only needs a collating sequence but also a
>statement of what symbols are equal for the first sort (but then must be
>post-sorted according to the sequence).
>
>Frankly, this is very different from what I've done in the past.  I imagine
>this comes up all the time in non-English-speaking countries.  How is it
>dealt with?
>
>+---------------------------------------------------------------+
>|    Dave Tutelman						|
>|    Physical - AT&T Bell Labs  -  Lincroft, NJ	  07738		|
>|    Logical -  dmt@pegasus.att.com -or- dtutelman@attmail.com	|
>|    Audible -  (908) 576 2194  (Office)			|
>|		(908) 922 9576  (Home)				|
>+---------------------------------------------------------------+


-- 
  \_\    Denis Beauregard  *  internet:beaurega@ireq.hydro.qc.ca
 /   \   Genealogiste officiel : Beauregard/Jarret/Jarest/Vincent
J   __>  Un Quebec renouvele dans une Amerique renovee
\_.-===                                                  Opinions ? Et pis non !