The Hamming Distance Option: Part 3 of Peter and the Postal Service

Hamming distance is a measure of the difference between strings of two equal length. Formally, the hamming distance between two strings is a count of the number of positions in which those strings differ. It is computed by traversing both strings, character by character, and counting the differing characters. Two strings with a hamming distance of zero are perfect matches.

Peter was shocked that the mailman had refused to deliver the letter to "Petee Fencer" because it was not a perfect match with his name. The 'e' at the end of the name was obviously supposed to be an 'r'. Sowhat if Peter had been the one to insist on perfect string matching? The mailman should have been able to pick up this error easily.

"Okay. New plan." started Peter. "Let me tell you about hamming distance…"

The mailman continued to smile politely. He was clearly enjoying this new game.

"Hamming distance is a measure of the distance between two strings. You go through each position and count how many of the characters are different. For example, the distance between "Petee" and "Peter" is 1 -- the last letters do not match."

"Okay." Agreed the mailman. "And the distance between 'Peter' and 'Puget' is 3, right? And the distance between 'Peter' and 'Smart' is 5, right?"

"Uh... yeah." confirmed Peter. Obviously the mailman was well versed in hamming distance. Peter wondered how he had had those two examples so readily available.

"What if the lengths of the strings are not equal?" the mailman asked. "Doesn't hamming distance apply to equal length strings?"

"Well... Yes. Technically, they are supposed to be equal length in order to compute hamming distance. I guess that we should be using a slightly different metric in that case..." commented Peter. He thought over the situation for a moment. "Let's just pretend they are the same length. Just add spaces to the end of shorter one until they are the same length."

"Really? Isn't that cheating?" The mailman gave Peter a shocked look. It was one thing to insist on using a specific metric to match mail, but it was another matter entirely to cheat with that metric.

Peter dismissed this concern. "Filter out all letters with hamming distance greater than 2."

"Are you sure?" the mailman asked.

Peter nodded.

"So you do not want anything to 'Mr P. Fencer'?" confirmed the mailman.

"Wait! Of course I do. That is obviously me. P is just an abbreviation." yelled Peter.

"But the hamming distance is much more than 2. In fact, it is 5. "Mr P. Fencer" and "Peter Fencer" do not match until the space before your last name." argued the mailman innocently.

"Yes, but…" started Peter.

"Nope." interrupted the mailman. "You told me to filter all names with a hamming distance greater than 2."

"Wait." Peter argued. "How about string edit distance?" he tried.

The mailman looked at him for a full minute. "Do you want the letter I have for 'Apprentice P. Fencer'? Or do you want to keep trying to help me improve my job?"

Peter sighed heavily. He had underestimated the complexities of string comparisons for mail delivery. He should have listened to the mailman's warning.

"If I apologize, can you go back to the algorithm that you were using before?" Peter asked.

The mailman looked at Peter for a moment. "I suppose I could. You know that it is not 100% accurate though, right? It even uses a few heuristics."

Peter nodded humbly.

From that day on, Peter started receiving all of his mail. He learned not to argue string comparison algorithms with postal carriers.

--------------

See how it started with Part 1 and Part 2 of Peter and the Postal Service.

Incorrectly Delivered Mail and Comparing Strings: Part 2 of Peter and the Postal Service

Strings are sequences of characters. In order for two strings to be identical, every character must match between the two strings. Thus, you can check whether two strings are identical by iterating over each position in the string and comparing the corresponding characters.

"Excuse me!" Peter shouted while running down the road after the mailman. "This letter is not addressed to me."

"It isn't?" asked the mailman. He looked annoyed at the interruption to his routine.

"No. It is not." confirmed Peter. "My name is Peter Fencer. This letter is for Paul Fencer"

"Eh... Sorry. They are close." replied the mailman.

"Close does not count!" objected Peter.

"Huh?" asked the mailman.

"When comparing two strings, you need to compare every single character. The two strings match if and only if every character is the same!" argued Peter.

The mailman looked at Peter skeptically. "Are you sure that you want to argue this with me?" he asked.

"I most certainly do." continued Peter. "Here is the algorithm you should be using:

IF the two strings are different lengths THEN one of them has extra (unmatched) characters at the end, so reject the match.

Otherwise, FOR EACH position in the string: compare the corresponding characters in each string. IF they are not the same, reject.

And if you reach the end of the strings without rejecting, then you have a match."

"Alright." said the mailman. "I will use that test from now on. What string do you want me to use for comparison?"

Peter smiled. He pulled out his new return address stamp, stamped a blank piece of paper, and handed it to the mailman. "This." he declared.

The mailman nodded and left.

For two blissful weeks everything seemed to go perfectly. Peter never had to chase the mailman down the street to return a piece of incorrectly addressed mail. Peter felt pride that he helped the mailman improve his job performance.

Then, Peter noticed that he was missing a very important letter from the head of the library association. He had been assured that it would arrive last week. He approached the mailman the next day.

"Excuse me. I am waiting for a letter from the library association. Have you seen it?" he asked.

"No. I have not seen anything from the library association that matched your address." answered the mailman. "There was something for a Petee Fencer, but not for Peter Fencer."

"Wait!" cried Peter. "That is me! It is obviously a typo. The 'r' probably looked like an 'e' on some list."

"That cannot be right. It does not pass the algorithm you gave me." argued the mailman innocently.

"Yes, but…" started Peter. He wanted to scream.

The mailman stood there politely smiling.

"Okay. New plan." started Peter. "Let me tell you about hamming distance…"

---------------------------

Learn more about strings by reading about Peter and his new address stamp.

Other updates: Illustrations added to "Hunting Dragons With Binary Search" and "President of the Heap".

Peter's Address Stamp (or Strings as Arrays of Characters): Part 1 of Peter and the Postal Service

String are sequences of characters. In fact, in many programming languages, strings are implemented as an array of characters. Thus, in many languages you can access each character as you would any value in an array. For example, in C you might write my_string[0] to access the first character and my_string[9] to access the tenth.

Peter's address was composed of exactly three lines and 37 characters:

Peter Fencer

100 Library Way

Alexandria

The first line had exactly 12 characters, the second line had 15 characters, and last line had exactly 10. Peter knew this for a fact, because he had spent the entire morning trying to order an address stamp.

The form was exactly what you would expect a form for an address stamp to look like. It had three different lines for the three different lines of his address. Each line had a neat label, such as "Name" or "City", followed by 15 blank squares. To complete the form, all you needed to do was fill in the squares with the correct letters of your address. It was really quite simple.

But, Peter had now spent three hours staring at the form.

The problem was that the Imperial Stamp and Scale Company charged by the character. Peter wanted to guarantee that he was writing his address in the fewest letters while still maintaining correctness. After the first hour, he had convinced himself that there was no way to safely shorten his name or city. The address was more of a gray zone. He debated shortening the "Way" to a "W", but ultimately decided against it. Avoiding confusion was worth 2 letters.

The other thing that bothered Peter was blank space at the end of the line. Would he be charged for them? The address strings had to allow for spaces as valid characters. For example, the sixth character in the name string was a space that separated his first and last name. He knew how to handle such cases on library forms: depending on the type of form, you either used a special character to terminate the string (a NULL character) or also wrote down the length of the string. It was easy to tell where the string ended. Although Peter logically knew that the company should simply drop the trailing spaces, he was irrationally worried that they would not.

Finally, after spending the morning fretting over the form, Peter mailed it. In 4 to 6 weeks, he would have a brand new return address stamp. He sighed with relief.

He deeply hoped that this stamp would help clear up some of the problems that he was having with his mail. He had recently discovered that his handwriting was so terrible that no one in the post office could read the addresses. His last letter, which was supposed to go to his neighbor, was routed to West Atlantis! Even worse, the same problem applied to the return addresses, which meant that his letters could not even be returned. So, at least this stamp would solve that problem.

What Peter did not realize is that this address stamp was simply the beginning of a long and epic debate over the how strings should be used in delivering the mail.

-----------------

See more of Peter and the Postal Service in Part 2: Incorrectly Delivered Mail and Comparing Strings.

For more more discussion about arrays, see how Zed used arrays in his coffee shop menus.