Hashing Characters

The previous page ends on a table nobody builds. Reading a text as its characters means giving every character an entry, and a table with an entry for every character Unicode has room for is complete in the way the byte table is complete, so nothing can ever be unfamiliar to it. The arithmetic is what stops it.

A model gives every entry a row of numbers to learn, and at an ordinary width of 768 those 1,114,112 entries come to 855,638,016 numbers, which is more than many whole models, for a table almost every row of which no text will ever reach.

Fitting the table to a corpus instead is what the previous page measured, and it is the failure this page starts from. Every character of our eighteen English sentences gives a table of 37 entries, which is cheap and covers English. Put one short sentence of Greek to it and 17 of the 21 characters come back as the stand-in, so the sentence arrives at the model as the fact that something unreadable was there, seventeen times over.

That gap does not close with a bigger corpus, since Han alone has tens of thousands of characters and whatever text we gather is finite.

A table has two jobs, and it is worth separating them, because only one of them is expensive. It holds what a model learned about each entry, which is the rows of numbers, and it holds the mapping from a piece of writing to which row that is. The mapping is the part that has to be built from a corpus, saved, shipped and kept in step with the model, and it is the part that can be unfamiliar with something.

Hashing removes the second job entirely. A character already has a number, the one Unicode gave it, and there is a piece of arithmetic that turns any whole number into a position inside a range we chose. Multiply it by a fixed odd number and take the remainder on dividing by the height of the table.

That is the whole mapping. It is a handful of instructions, it stores nothing, it was fitted to nothing, and it answers for a character from a script nobody has ever put to it in exactly the same time it answers for the letter e.

bucket  =  ((character number + 1) × multiplier)  mod  buckets

The height of the table, which the rest of this page calls the number of buckets, is now a setting rather than a discovery. It is fixed before any writing is read and it does not move when more is. That is the change worth holding on to, since the size of every table on the page above was decided by what some text happened to contain.

Two characters can be sent to the same bucket, and when that happens the model sees one row where there were two characters. A table built by listing what a corpus contained never does this, since it gives each entry its own position by construction. So the trade is set out from the beginning. We are buying a table whose height we chose and which is never surprised, and we are paying for it with characters that become one thing.

How many of them do that depends only on the height, and Part 3 counts them. What matters at this point is that the loss is invisible from inside. A learned table announces an unfamiliar piece by handing back a stand-in, so a reader can count them and see the damage; a hash hands back a perfectly ordinary-looking bucket whether or not something else is already living there.

Take the letter a. Unicode calls it 97, the rule adds one to give 98, and then 98 is multiplied by each of eight fixed odd numbers and each product is reduced by the height of the table. The eight multipliers are the small primes 31, 43, 59, 61, 73, 97, 103 and 113, and at 16,384 buckets none of the eight products reaches the height, so none of them is reduced at all and the buckets are the products themselves.

98 × 31  =   3038      98 × 73  =   7154
98 × 43  =   4214      98 × 97  =   9506
98 × 59  =   5782      98 × 103 =  10094
98 × 61  =   5978      98 × 113 =  11074

Eight numbers for one character needs explaining, and section 12 is where the reason is examined properly. The short version is that the model is given eight tables of 96 numbers each rather than one table of 768, and a character’s row is the eight slices joined end to end, so the total width is the same and the hope is that two characters agreeing in one slice still differ in the other seven.

Our sentence is 51 characters long. Every one of them goes through the same short piece of arithmetic, and here are the first four, with each character’s number and the bucket the first multiplier sent it to.

Dr. Alvarez didn't expect the low-cost re-analysis.

D    69 × 31  =  2139
r   115 × 31  =  3565
.    47 × 31  =  1457
␣    33 × 31  =  1023

Across the whole sentence that comes to 51 positions and 408 numbers, since each position carries eight. The table behind them has 16,384 rows whatever we put in the box, and at a width of 768 those rows come to 12,582,912 numbers, which is a sixty-eighth of what the complete character table would have cost and is the same figure for a page of Greek. Twenty-four distinct characters appear in the sentence and they produce twenty-four distinct sets of buckets, so at this width nothing in it was lost.

eight tables = 8 × 16,384 × 96 = 12,582,912 values
one table    = 16,384 × 768 = 12,582,912 values

Put the Greek sentence through the same arithmetic and the contrast with section 1 is complete. All 21 characters get buckets, none of them is a stand-in, and the text comes back character for character. The same holds for the Chinese sentence, for a script invented next year, and for a character Unicode has assigned nothing to at all, since the rule takes a number and returns a number and has no opinion about what the number stands for.

It is worth being careful about what has been settled there, because the previous page drew the same line and it matters more here. Every character can be turned into buckets and every text can be given back, since the character numbers are kept beside the buckets and it is those that decoding reads. What has not been settled is whether a model trained on English knows anything about the rows a Greek letter lit. Representable and learnable are separate questions, and only the first of them has an answer here.

Sequence length is what everything downstream is charged in, so it is the first number to check. This arrangement gives one position per character, which is what the character reading on the previous page gave and is not what the byte reading gives, since a character can take up to four bytes. On English the two agree and on nothing else do they.

The Chinese sentence is where the difference is widest. It costs 6 positions here and 18 as bytes, so anything that compares every position with every other position does a ninth of the work, and the fitted character table would have spelled all six of its characters as the stand-in. Hindi goes from 48 down to 18. English pays exactly the same either way and gains nothing from any of this.

Here is the thing section 3 warned about, at the published settings and with the two characters named. The capital letter A is character number 65. The Han ideograph 䁁 is character number 16,449. At 16,384 buckets those two produce the identical eight numbers, in the same order, and a ninth hash from the same family would not separate them either.

A       2046  2838  3894  4026  4818  6402  6798  7458
䁁      2046  2838  3894  4026  4818  6402  6798  7458

A        66 × 31  =  2046
䁁   16,450 × 31  =  509,950
509,950 − (31 × 16,384)  =  509,950 − 507,904  =  2046

What a model can no longer do is worth spelling out. It cannot learn that one of these begins an English sentence and the other does not. It cannot give them different rows, since they ask for the same rows. Whatever it learns about the sequence “A” it also learns about “䁁”, and any gradient that would push the two apart pushes on one set of numbers and moves both. The two characters have become one character as far as everything above the tokenizer is concerned.

Since each hash multiplies and then takes a remainder, two character numbers land in the same bucket under a given hash exactly when their difference is a multiple of the height, or of a divisor of the height where the multiplier and the height share a factor. At 16,384 the multipliers share nothing with the height, so the condition is the same for all eight hashes at once, and two characters agree everywhere or nowhere.

This hash construction repeats its complete bucket pattern after 16,384 code points. Count how many repetitions fit in the Unicode code-point range.

repetitions = 1,114,112 / 16,384 = 68
other code points sharing a pattern = 68 − 1 = 67

These are code points, including unassigned values. Each example character therefore shares its complete hash pattern with sixty-seven others; for A, ten of those others are assigned characters in the data used here.

Compare the two ways a reading can lose something. A table fitted to a corpus meets a character it does not hold, returns the stand-in, and the stand-in is visible in the numbers, so a caller can count them, decode the text and see exactly what came back wrong. On the Greek sentence there were 17 of them, and reading the numbers back gave 17 stand-ins where letters had been.

A hash produces no such signal. Bucket 2046 looks the same whether one character sends something there or a hundred do, and nothing in the eight numbers a model reads says how crowded they are. The text still comes back exactly, because the character numbers travelled alongside; it is the model’s view that lost the distinction, and the model has no way of asking.

So a collision is not detected, not reported and not repaired at training time, and the ceiling it puts on what the model can learn was fixed by an arithmetic accident before the first text arrived.

It is fair to ask whether any of this touches ordinary writing, and on the running sentence at the published height it does not. The sentence uses 24 distinct characters, they produce 24 distinct sets of buckets, and every one of the 68 characters sharing any of those sets is somewhere else in the space entirely. A collision needs two characters 16,384 apart and the sentence spans about a hundred.

Narrowing the table brings it into view. At 64 buckets the full stop and the letter n land on the same eight numbers, so the 24 distinct characters come out as 23 distinct sets. At 32 buckets three pairs go, D with d, the full stop with n, and A with a, and the sentence arrives at the model with 21 kinds of character in it rather than 24. Set the playground to those widths and the merged characters are marked in the strip.

The standard answer to everything in Part 3 is to hash more than once. Give a character eight buckets from eight different hashes and let the model join eight narrow slices into one row. Two characters that collide under one hash are then still separated by the other seven, and the chance of two characters agreeing in all eight is the chance of agreeing in one raised to the eighth power, which at 16,384 buckets is a number with thirty-three zeros after the point.

That argument is correct for hashes whose collisions are independent, and it is the argument the eight in the published arrangement rest on. It costs nothing in parameters, as section 5 showed, so it looks like eight chances for the price of one, and it is the sort of thing a reader accepts without checking.

The measurement that settles it is a count rather than an estimate. Run every one of the 1,114,112 characters through the arrangement, collect the set of buckets each one produces, and count how many different sets come out. That number is exactly how many kinds of character the arrangement can tell apart, and a defence that works should raise it.

At 16,384 buckets, one hash produces 16,384 distinct sets. Two hashes produce 16,384. Four produce 16,384, and eight produce 16,384. The eight hashes buy no separation whatever at the published settings, and the seven extra ones leave the arrangement exactly where the first one left it.

…

The chart is the sweep across seven heights, with four bars to a height. In three of the seven the four bars are identical because one hash already reaches the most any arrangement of that height could reach. In the other four the first bar falls short and the second reaches the edge, and in none of the seven does anything change after the second bar.

The reason is visible in the rule and does not need the experiment, though the experiment is what made me look. Every hash multiplies the same quantity, the character number plus one, and reduces by the same height. Reducing by the height at the end means the product only ever depended on the character number through its own remainder on dividing by the height, so every hash reads the character through the same small window.

two characters differ by a multiple of the height
  ⇒  every multiplier sends them to one bucket
  ⇒  no number of hashes tells them apart

Which gives a ceiling rather than a probability. Whatever the number of hashes, the arrangement can distinguish at most as many kinds of character as there are buckets, because each character is read only through a value in that range. Eight hashes at 16,384 buckets cannot see more than 16,384 kinds of thing, and one hash already sees all of them, which is why the bars are the same length.

Choose ninety-three buckets and multiplier thirty-one. These numbers share a factor, so multiplication followed by the remainder operation cannot reach every bucket.

93 = 3 × 31
possible residues of 31x modulo 93: 0, 31, 62

One such hash distinguishes only three classes of code points. This gives a concrete case for testing whether another hash adds information.

Now bring in the second multiplier, 43, which shares nothing with 93. It shuffles the remainders rather than collapsing them, so the pair of hashes together distinguishes all 93, which is the ceiling. The second hash took the arrangement from 3 to 93 and the third through eighth took it no further, because there was nowhere further to go.

One case proves the condition is real and says nothing about how often it bites, so I counted that too, over every height from 2 to 2,000. A single hash falls short of its ceiling at 64 of those 1,999 heights, and all 64 are multiples of 31, which is the first multiplier and is what the argument in section 14 predicts. That is a little over three per cent of the widths anybody might choose.

Two hashes fall short at none of them. Not a few, not a handful, none, across all 1,999 heights. So for this family the third hash and every hash after it are provably worth nothing at any width whatever, and the second is worth something only where the first multiplier happens to divide the height. The published arrangement chose a power of two, which no odd multiplier divides, so it is in the ninety-seven per cent where even the second buys nothing.

The same move applies one level up, and it is worth a section because it buys something the character version cannot. Wrap a word in a boundary mark, cut it into every run of three characters, hash each of those runs into a bucket, and let the word be the set of buckets that came up. A word of n characters gives n runs, so the word cat wrapped as _cat_ gives _ca, cat and at_.

What arrives at the model is a set rather than a sequence, and a word’s row is the sum of the rows of its active buckets. Two words spelled alike share pieces, so they share buckets, so they share rows before any training has happened at all. That overlap is the point of doing it this way, and it is free.

At 8,192 buckets and one hash, cat lights three buckets and cats lights four, and two of them are the same two. The shared ones are the pieces the two words share, _ca and cat, and the difference is that cat ends with at_ where cats has ats and ts_.

cat    _ca  cat  at_          2002   5665   6052
cats   _ca  cat  ats  ts_    1676   2002   5665   6072

The effect survives longer words and heavier changes. The word analysis lights 8 buckets and reanalysis lights 10, and 7 of them are shared, so a model meeting reanalysis for the first time already holds seven of the eight rows it built for analysis. Cost and costs share 3 of 4 and 5.

In positions this is the cheapest reading on either of these two pages. Our sentence becomes 7 positions, one per whitespace word, against 25 under a vocabulary merged from the eighteen sentences and 51 under either character reading. What is spent instead is lookups, since those 7 positions light 45 buckets between them and each one is a row fetched and added.

The pieces do not spread evenly, and the count is worth having because it is the collision question again in a new place. Twenty-six lowercase letters and the boundary mark make 19,683 possible runs of three, and at 8,192 buckets those fall into 8,122 of the 8,192, with 2.423 to a bucket on average and 5 in the heaviest. The run nal, which is inside our own word re-analysis, shares bucket 3245 with yme and with aaa.

Whether that matters depends on whether the collisions land in the same word, and mostly they do not. Across all 17,576 three-letter words at a deliberately narrow 512 buckets there are 17,570 distinct fingerprints, so 6 pairs of words are genuinely indistinguishable, fek with hab among them. A word lights several buckets and two words have to agree on all of them, which is a much harder coincidence than one piece landing on another.

A set of buckets is not a word, and nothing reads one back. Many words produce a given fingerprint and the method holds no list of which, so recovering the word means keeping a list of candidate words, fingerprinting each and answering with whichever candidate matches best. That list is a fact about the task rather than about the method, which is why the method offers a way of comparing two fingerprints and no way of decoding one.

And a set cannot count. The word aaa gives the pieces _aa, aaa and aa_, and aaaa gives _aa, aaa, aaa and aa_, which is the same three once the repeat is dropped, so those two words have exactly the same fingerprint at any width whatever and aaaaa has it too. The boundary is precise rather than general. The words baa and baaa do differ, because the extra letter there produced the run aaa which the shorter word did not have.

Every other reading in this section can be run backwards. A byte number names one byte, an entry of a merged vocabulary names one piece of writing, and reading the numbers back is a lookup. Ask which character a set of buckets stands for and the question has no single answer, since the map from characters to sets is many to one by construction, and at 16,384 buckets it is exactly 68 to one.

So there is nothing here to argue about and no implementation choice to make. The information was destroyed by the remainder step and no procedure recovers it. Any arrangement that wants its text back has to carry the character numbers alongside the buckets, which is what happens in practice, and it means the claim “no vocabulary” is a claim about the model’s table rather than about the pipeline. The characters are still there; they are simply not what the model reads.

Everything on this page turns on one number and nothing on this page determines it. Raising the height multiplies the rows and divides the crowd in exact proportion, and the two move smoothly against each other with no corner anywhere, so there is no height at which something changes character and no height a derivation arrives at.

…

What can be said is what each end costs. At 256 buckets the rows cost the same 196,608 as the byte table and every set of buckets stands for 4,352 characters, which is a model that cannot tell most letters apart. At 262,144 the crowd is down to 4.25 characters to a set and the rows have reached 201,326,592, which is nearly a quarter of the complete table this page set out to avoid.

Somewhere in between is a choice, and it is a choice about which scripts the model is expected to read rather than a fact about hashing.

There is one limit here that no width fixes and it is not a degenerate input at all. Characters are related to one another in ways a table could hold. The capital and lowercase forms of a letter behave alike, the ten digits behave alike, the accented variants of a Latin letter behave more like it than like anything else. A learned table can put those rows near each other and a character usually seen in one context can drift towards the characters it appears beside.

The hash destroys every one of those relationships on the way in. A and a differ by 32 in their character numbers, so at 16,384 buckets they land 32 multiplied by each multiplier apart, in positions with no more in common than any other pair. Two characters that behave identically gain nothing whatever from that, and the model has to learn each of their rows from scratch and separately. Whatever regularity the writing system had is outside what this arrangement can express.

The arithmetic is orderly even so, which turns out not to help. Consecutive characters land in buckets exactly one multiplier apart, so a is 3038 under the first hash and b is 3069, and every run of the alphabet is an evenly spaced run of buckets. Rows of a table have no order among themselves, so a model reading row 3038 has no way of noticing that b sits 31 rows further on, and the twenty-six letters lie in an arithmetic progression that nothing above the table can see.

Gathered in one place, these are the inputs and the settings on which the method stops being defined rather than becoming approximate, together with what has to be decided in each case and what turns on the decision. The ones with a genuine choice attached are the ones worth attention, since nothing in the arithmetic makes them and somebody has to.