Reverse Engineering Sort Order

[qq]

Hi Reverend Monks:

I want to determine a bi level sort order from a given set of already sorted records for use with Sort::ArbBiLex. (Well, actually a drop in replacement that I've written.)

The existing records are first name, last name have escaped entity sequences in them in the form: é.

I think this might be an interesting problem - but excuse the long post.

Sort::ArbBiLex has a very well written explanation of what bi level sorting is, and why you have to do it.

Decleration format and usage is like:

use Sort::ArbBiLex (
    'fulani_sort',   # ask for a &fulani_sort to be defined
    "a A
     c C
     ch Ch CH
     ch' Ch' CH'
     e E
     l L
     lh Lh LH
     n N
     r R
     s S
     u U
     z Z
    "
  );
  @words = <>;
  @stuff = fulani_sort(@words);
  foreach (@stuff) { print "<$_>\n" }

The decleration form above is just a shorter way of writing an AoA. Its that decleration, or at least a good approximation, that I'm hoping to extract from existing records (see DATA below).

The resulting decleration does not have to be perfect, it will be checked by hand.

Solution:

Well, if I knew I wouldn't be writing this.

First step, I believe, is to extract a list of glyghs from the data. Since glyghs can be variable widths, you can't do this entirely automatically. For my purposes, since all glyghs longer than one character are easily matched, this is easy. Put them as keys to a hash to remove duplicates (%glyghs below).

Next step I'm lost. I think something like:

1. build a list of first glyphs of last name
2. build a list af second glyphs of last name
3. repeat, giving:

    A, B, D
    L, N, R, A, E
    B, C, D, R, B, I, A, ’, C
    E, A, R, O, I, N, R, A, C

4. do something clever

but some glyphs are 'equal' on the first level sort. Ie we want an AoA, not just an array. And some glyphs might be invisible to the sort order - ep whitespace or '&rsquo';

#/usr/bin/perl -w

use strict;

my %glyphs;
my @words;
while  ( <DATA> ) {
    push @words, split /,\s*/;
}

@glyphs{ map { /(&.+?;)|(.)/g } @words } = 1; 
print join( "\n", keys %glyphs);

__DATA__
ALBEVERIO MANZONI,     Solvejg
ALCAL&Aacute;,         Kathleen
ANDR&Eacute;E,         Alice
ARROYO-GOMEZ,         Mario Vernon
BABINEAU,             Jean Joseph
BAINBRIDGE,         Dame Beryl (Margaret)
BAINBRIDGE,         Cyril
DEARDEN,             James Shackley
DE&rsquo;ATH,         Richard
DECKER,             Donna

Thanks for you're ideas, qq