CHARACTER LENGTH

All characters used to construct the charset must have the same length, but need not neccessarily be one byte/char long.

COMPLEXITY

The complexity for converting from number to string, and vice versa, is O(N), with N beeing the number of characters in the string.

Actually, it is a bit higher, since the underlying Math::BigInt needs more time for longer numbers than for shorts. But usually the practically string length limit is reached before this effect shows up.

See BENCHMARKS in Math::String for run-time details.

STRING ORDERING

With a simple charset, converting between the number and string is relatively simple and straightforward, albeit slow.

With bigrams, this becomes even more complex. But since all the information on how to convert between number and string in inside the charset definition, Math::String::Charset will produce (and sometimes cache) this information. Thus Math::String is simple a hull around Math::String::Charset and Math::BigInt.

SIMPLE CHARSETS

Depending on the charset, the order in which Math::String 'sees' the strings is different. Example with charset 'A'..'D':

          A      1
          B      2
          C      3
          D      4
         AA      5
         AB      6
         AC      7
         AD      8
         BA      9
         BB     10
         BC     11
         ..
        AAA     20
        AAB     21 etc

The order of characters does not matter, 'B','D','C','A' will produce similiar results, though in a different order inside Math::String:

          B      1
          D      2
          C      3
          A      4
         BB      5
         BD      6
         BC      7
         ..
        BBB     20
        BBD     21 etc

Here is an example with characters of length 3:

        foo      1
        bar      2
        baz      3
     foofoo      4
     foobar      5
     foobaz      6
     barfoo      7
     barbar      8
     barbaz      9
     bazfoo     10
     bazbar     11
     bazbaz     12
  foofoofoo     13 etc

All charset items must have the same length, unless you use a separator string:

        use Math::String;
        $a = Math::String->new('',
          { start => [ qw/ the green car a/ ], sep => ' ' } );
        while ($b ne 'the green car')
          {
          $a ++;
          print "$a\t";         # print "a green car" etc
          }

The separator is a string, not a regexp and it must not be present in any of the characters of the charset.

The old way was using a fill character, which is more complicated:

        use Math::String;
        $a = Math::String->new('', [ qw/ the::: green: car::: a:::::/ ]);
        while ($b ne 'the green car')
          {
          $a ++;
          print "$a\t";         # print "a:::::green:car:::" etc
          $b = "$a"; $b =~ s/:+/ /g; $b =~ s/\s+$//;
          print "$b\n";         # print "a green car" etc
          }

This produces:

        the:::  the
        green:  green
        car:::  car
        a:::::  a
        the:::the:::    the the
        the:::green:    the green
        the:::car:::    the car
        the:::a:::::    the a
        green:the:::    green the
        green:green:    green green
        green:car:::    green car
        green:a:::::    green a
        car:::the:::    car the
        car:::green:    car green
        car:::car:::    car car
        car:::a:::::    car a
        a:::::the:::    a the
        a:::::green:    a green
        a:::::car:::    a car
        a:::::a:::::    a a
        the:::the:::the:::      the the the
        the:::the:::green:      the the green
        the:::the:::car:::      the the car
        the:::the:::a:::::      the the a
        the:::green:the:::      the green the
        the:::green:green:      the green green
        the:::green:car:::      the green car

HIGHER ORDERS

Now imagine a charset that is defined as follows:

Starting characters for each string can be 'a','c','b' and 'd' (in that order). Each 'a' can be followed by either 'b', 'c' or 'a' (again in that order), each 'c can be followed by either 'c', 'd' (again in that order), and each 'b' or 'd' can be followed by an 'a' (and nothing else).

The definition is thus:

        use Math::String::Charset;
        $cs = Math::String::Charset->new( {
                start => [ 'a', 'c', 'b', 'd' ],
                bi => {
                  'a' => [ 'b','c','a' ],
                  'b' => [ 'a', ],
                  'd' => [ 'a', ],
                  'c' => [ 'c','d' ],
                  }
                } );

This means that each character in a string depends on the previous character. Please note that the probabilities on which characters follows how often which character do not concern us here. We simple enumerate them all. Or put differently: each probability is 1.

With the charset above, the string sequence runs as follows:

        string  number  count of strings
                        with length
          a       1
          c       2
          b       3
          d       4     1=4
         ab       5
         ac       6
         aa       7
         cc       8
         cd       9
         ba      10
         da      11     2=7
        aba      12
        acc      13
        acd      14
        aab      15
        aac      16
        aaa      17
        ccc      18
        ccd      19
        cda      20
        bab      21
        bac      22
        baa      23
        dab      24
        dac      25
        daa      26     3=15
       abab      27
       abac      28
       abaa      29
       accc      30
       accd      31
       acda      32
       aaba      33
       aacc      34
       aacd      35     etc

There are 4 strings with length 1, 7 with length 2, 15 with length 3 etc. Here is an example for first() and last():

        $charset->first(3);     # gives aba
        $charset->last(3);      # gives daa

RESTRICTING STRING ENDINGS

Sometimes, you want to specify that a string can end only in certain characters. There are two ways:

        use Math::String::Charset;
        $cs = Math::String::Charset->new( {
                start => [ 'a', 'c', 'b', 'd' ],
                bi => {
                  'a' => [ 'b','c','a' ],
                  'b' => [ 'a', ],
                  'd' => [ 'a', ],
                  'c' => [ 'c','d' ],
                  }
                end => [ 'a','b' ],
                } );

This defines any string ending not in 'a' or 'b' as invalid. The sequence runs thus:

        string  number  count of strings
                        with length
          a       1
          b       2     2
         ab       4
         aa       5
         ba       6
         da       7     4
        aba       8
        aab       9
        aaa      10
        cda      11
        bab      12
        baa      13
        dab      14
        daa      15     8
       abab      16
       abaa      17     etc

There are now only 2 strings with length 1, 4 with length 2, 8 with length 3 etc.

The other way is to specify the (additional) ending restrictions implicit by using chars that are not followed by other characters:

        use Math::String::Charset;
        $cs = Math::String::Charset->new( {
                start => [ 'a', 'c', 'b', 'd' ],
                bi => {
                  'a' => [ 'b','c','a' ],
                  'b' => [ 'a', ],
                  'd' => [ 'a', ],
                  'c' => [  ],
                  }
                } );

Since 'c' is not followed by any characters, there are no strings with a 'c' in the middle (which means strings can end in 'c'):

        string  number  count of strings
                        with length
          a       1
          c       2
          b       3
          d       4     4
         ab       5
         ac       6
         aa       7
         ba       8
         da       9     5
        aba      10
        aab      11
        aac      12
        aaa      13
        bab      14
        bac      15
        baa      16
        dab      17
        dac      18
        daa      19     10
       abab      20
       abac      21 etc

There are now 4 strings with length 1, 5 with length 2, 10 with length 3 etc.

Any character that is not followed by another character is automatically added to "end". This is because otherwise you would have created a rendundand character which could never appear in any string:

Let's assume 'q' is not in the "end" set, and not followed by any other character:

1.

There can no string "q", since strings of lenght 1 start and end with their only character. Since 'q' is not in "end", the string "q" is invalid (no matter wether 'q' appears in "start" or not).

2.

No string longer than 1 could start with 'q' or have a 'q' in the middle, since 'q' is not followed by anything. This leaves only strings with length 1 and these are invalid according to rule 1.

CONVERTING (STRING <=> NUMBER)

From now on, a 'class' refers to all strings with the same length. The order or length of a class is the length of all strings in it.

With a simple charset, each class has exactly M times more strings than the previous class (e.g. the class with a length - 1). M is in this case the length of the charset.

SIMPLE CHARSET

To convert between string and number, we must simple know which string has which number and which number is which string. Although this sounds very difficult, it is not so. With 'simple' charsets, it only involves a bit of math.

First we need to know how many string are in the class. From this information we can determine the lenght of a string given it's number, and get the range inside which the number to a string lies:

Let's stick to the example with 4 characters above, 'A'..'D':

        Stringlenght    strings with that length        first in range
        1               4                               1
        2               16 (4*4)                        5
        3               64 (4*4*4)                      21
        4               4**4                            85
        5               4**5 etc                        341

You see that this is easy to calculate. Now, given the number 66, we can determine how long the string must be:

66 is greater than 21, but lower than 85, so the string must be 3 characters long. This information is determined in O(N) steps, wheras N is the length of the string by successive comparing the number to the elements in all string of a certain length.

If we then subtract from 66 the 21, we get 45 and thus know it must be the fourty-fifth string of the 3 character long ones.

The math involved to determine which 3 character-string it actually is equally to converting between decimal and hexadecimal numbers. Please see source for the gory, but boring details.

HIGHER ORDER CHARSETS

For charsets of higher order, even determining the number of all strings in a class becomes more difficult. Fortunately, there is a way to do it in N steps just like with a simple charset.

BASED ON ENDING COUNTS

The first way is based on the observation that the number of strings in class n+1 only depends on the number of ending chars in class n, and nothing else.

This is, however, not used in the current implemenation, since there is a slightly faster/simpler way based on the count of strings that start with a given character in class n, n-1, n-2 etc. See below for a description.

Here is for reference the example with ending char counts:

        use Math::String::Charset;
        $cs = Math::String::Charset->new( {
                start => [ 'a', 'c', 'b', 'd' ],
                bi => {
                  'a' => [ 'b','c','a' ],
                  'c' => [ 'c','d' ],
                  'b' => [ 'a', ],
                  'd' => [ 'a', ],
                  }
                } );
        Class 1:
          a       1
          c       2
          b       3
          d       4     4

As you can see, there is one 'a', one 'c', one 'b' and one 'd'. To determine how many strings are in class 2, we must multiply the occurances of each character by the number of how many characters it is followed:

        a * 3 + c * 2 + d * 1 + b * 1

which equals

        1 * 3 + 1 * 2 + 1 * 1 + 1 * 1

If we summ this all up, we get 3+2+1+1 = 7, which is exactly the number of strings in class 2. But to determine now the number of strings in class 3, we must now how many strings in class 2 end on 'a', how many on 'b' etc.

We can do this in the same loop, by not only keeping a sum, but by counting all the different endings. F.i. exactly one string ended in 'a' in class 1. Since 'a' can be followed by 3 characters, for each character we know that it will occure at least 1 time. So we add the 1 to the character in question.

        $new_count->{'b'} += $count->{'a'};

This yields the amounts of strings that end in 'b' in the next class.

We have to do this for every different starting character, and for each of the characters that follows each starting character. In the worst case this means M*M steps, while M is the length of the charset. We must repeat this for each of the classes, so that the complexity becomes O(N*M*M) in the worst case. For strings of higher order this gets worse, adding a *M for each higher order.

For our example, after processing 'a', we will have the following counts for ending chars in class 2:

        b => 1
        c => 1
        a => 1

After processing 'c', it is:

        b => 1
        c => 2 (+1)
        a => 1
        d => 1 (+1)

because 'c' is followed by 'd' or 'c'. When we are done with all characters, the following count's are in our $new_count hash:

        b => 1
        c => 2
        a => 3
        d => 1

When we sum them up, we get the count of strings in class 2. For class 3, we start with an empty count hash again, and then again for each character process the ones that follow it. Example for a:

        b => 0
        c => 0
        a => 0
        d => 0

3 times ending in 'a' followed by 'b','c' or 'd':

        b => 3  (+3)
        c => 3  (+3)
        a => 3  (+3)
        d => 0

2 times ending 'c' followed by 'c' or 'd':

        b => 3
        c => 5  (+2)
        a => 3
        d => 2  (+2)

After processing 'b' and 'd' in a similiar manner we get:

        b => 3
        c => 5
        a => 5
        d => 2

The sum is 15, and we know now that we have 15 different strings in class 3. The process for higher classes is the same again, re-using the counts from the lower class.

BASED ON STARTING COUNTS

The second, and implemented method counts for each class how many strings start with a given character. This gives us two information at once:

• A string of length N and a starting char of X, which number it must have at minimum (by summing up the counts of all strings that come before X) and how many strings are there starting with X (although this is not used for X, but only for all strings that come after X).
• How many strings are there with a given length, by summing up all the counts for the different starting chars.

This method also has the advantage that it doesn't need to re-calculate the count for each level. If we have cached the information for class 7, we can calculate class 8 right-away. The old method would either need to start at class 1, working up to 8 again, or cache additional information of the order N (where N is the number of different characters in the charset).

Here is how the second method works, based on the example above:

                start => [ 'a', 'c', 'b', 'd' ],
                bi => {
                  'a' => [ 'b','c','a' ],
                  'c' => [ 'c','d' ],
                  'b' => [ 'a', ],
                  'd' => [ 'a', ],
                  }

The sequence runs as follows:

        String  Strings starting with
                this character in this level
          a     1
          c     1
          b     1
          d     1
         ab
         ac
         aa     3       (1+1+1)
         cc
         cd     2       (1+1)
         ba     1
         da     1
        aba
        acc
        acd
        aab
        aac
        aaa     6       1 (b) + 2 (c) + 3 (a)
        ccc
        ccd
        cda     3       2 (c) + 1 (d)
        bab
        bac
        baa     3
        dab
        dac
        daa     3
       abab
       abac
       abaa
       accc     etc

As you can see, for length one, there is exactly one string for each starting character.

For the next class, we can find out how many strings start with a given char, by adding together all the counts of strings in the previous class.

F.i. in class 3, there are 6 strings starting with 'a'. We find this out by adding together 1 (there is 1 string starting with 'b' in class 2), 2 (there are two strings starting with 'c' in class 2) and 3 (three strings starting with 'a' in class 2).

As a special case we must throw away all strings in class 2 that have invalid ending characters. By doing this, we automatically have restricted all strings to only valid ending characters. Therefore, class 1 and 2 are setup upon creating the charset object, the others are calculated on-demand and then cached.

Since we are calculating the strings in the order of the starting characters, we can sum up all strings up to this character.

        String  First string in that class
          a     0
          c     1
          b     2
          d     3
         ab     0
         ac
         aa
         cc     3
         cd
         ba     5
         da     6
        aba     0
        acc
        acd
        aab
        aac
        aaa
        ccc     6
        ccd
        cda
        bab     9
        bac
        baa
        dab     12
        dac
        daa
       abab     0
       abac
       abaa
       accc     etc

When we add to the number of the last character (f.i. 12 in case of 'd' in class 3) the amount of strings with that character (here 3), we end up with the number of all strings in that class.

Thus in the same loop we calculate:

how many stings start with a given character in this class

what is the first number of a string starting with 'x' in that class

how many strings are in this class at all

That should be all we need to know to convert a string to it's number.

HIGHER ORDER CHARSETS, FINDING THE RIGHT NUMBER

From the section above we know that we can find out which number a string of a certain class has at minimum and at maximum. But what number has the string in that range, actually?

Well, given the information it is easy. First, find out which minimum number a string has with the given starting character in the class. Add this to it's base number. Then reduce the class by one, look at the next character and repeat this. In pseudo code:

        $class = length ($string); $base = base_number->[$class];
        foreach ($character)
          {
          $base += $sum->[$class]->{$character};
          $class --;
          }

So, after N simple steps (where N is the number of characters in the string), we have found the number of the string.

HIGHER ORDER CHARSETS, FINDING THE RIGHT STRING

Section not ready yet.

MULTIPLE MULTIWAY TREES

It helps to imagine the strings like a couple of trees (ASCII art is crude):

        class:  1   2    3   etc
       number
        1       a
          5     +--ab
           12   |   +--aba
          6     +--ac
           13   |   +--acc
           14   |   +--acd
          7     +--aa
           15       +--aab
           16       +--aac
           17       +--aaa
        2       c
          8     +--cc
           18   |   +--ccc
           19   |   +--ccd
          9     +--cd
           20       +--cda
        3       b
         10     +--ba
           21       +--bab
           22       +--bac
           23       +--baa
        4       d
         11     +--da
           24       +--dab
           25       +--dac
           26       +--daa

As you can see, there is a (independend) tree for each of the starting characters, which in turn contains independed sub-trees for each string in the next class etc. It is interesting to note that each string deeper in the tree starts with the same common starting string, aka 'd', 'da', 'dab' etc.

With a simple charset, all these trees contain the same number of nodes. With higher order charsets, this is no longer true.