Phonetic Algorithm: Bryan, Brian, Briane, Bryne, or … what was his name again?

Let the spelling loose …

What do Callie and Kelly have in common (except for the double ‘l’ in the middle)? What about “no” and “know”, or “Ceasar’s” and “scissors” and what about “message” and “massage”? You definitely got it – Callie and Kelly, “no” and “know”, “Ceasar’s” and “scissors” sound alike, but are spelled quite differently. “message” and “massage” on the other hand differ by only one vowel (“a” vs “e”) but their pronunciation is not at all the same.

It’s a well known fact for many languages that ortography does not determine the pronunciation of words. English is a classic example. George Bernard Shaw was the attributed author of “ghoti” as an alternative spelling of “fish”. And while phonology often reflects the current state of the development of the language, orthography may often lag centuries behind. And while English is notorious for that phenomenon it is not the only one. Swedish, French, Portuguese, among others, all have their ortography/pronunciation discrepancies.

Phonetic Algorithms

So how do we represent things that sound similar but are spelled different? It’s not trivial but for most cases it is not impossible either. Soundex is probably the first algorithm to tackle this problem. It is an example of the so called phonetic algorithms which attempt to solve the problem of giving the same encoding to strings which are pronounced in a similar fashion. Soundex was designed for English only but has its limits. DoubleMetaphone (DM) is one of the possible replacements and relatively successful. Designed by Lawrence Philips in the beginning of 1990s it not only deals with native English names but also takes proper care of foreign names so omnipresent in the language. And what is more – it can output two possible encodings for a given name, hence the “Double” in the naming of the algorithm, – an anglicised and a native (be that Slavic, Germanic, Greek, Spanish, etc.) version.

By relying on DM one can encode all the four names in the title of this post as “PRN”. The name George will get two encodings – JRJ and KRK, the second version reflecting a possible German pronunciation of the name. And a name with Polish origin, like Adamowicz, would also get two encodings – ATMTS and ATMFX, depending on whether you pronounce the “cz” as the English “ch” in “church” or “ts” in “hats”.

The original implementation by Lawrence Philips allowed a string to be encoded only with 4 characters. However, in most subsequent
implementations of the algorithm this option is parameterized or just omitted.

Apache Commons Codec has an implementation of the DM among others (Soundex, Metaphone, RefinedSoundex, ColognePhonetic, Coverphone, to
name just a few.) and here is a tiny example with it:

import org.apache.commons.codec.language.DoubleMetaphone;

public class DM {

public static void main(String[] args) {

String s = "Adamowicz";

DoubleMetaphone dm = new DoubleMetaphone();

// Default encoding length is 4!

// Let's make it 10

dm.setMaxCodeLen(10);

System.out.println("Alternative 1: " + dm.doubleMetaphone(s) +

// Remember, DM can output 2 possible encodings:

"nAlternative 2: " + dm.doubleMetaphone(s, true));

}
}

The above code will print out:

Alternative 1: ATMTS

Alternative 2: ATMFX

It is also relatively straightforward to do phonetic search with Solr. You just need to ensure that you add the phonetic analysis to a field which contains names in your schema.xml:

Enhancements

While DM does perform quite well, at first sight, it has its limitations. We should know that it still originated from the English language and although it aims to tackle a variety of non-native borrowings most of the rules are English-centric. Suppose you work on any of the Scandinavian languages (Swedish, Danish, Norwegian, Icelandic) and one of the names you want to encode is “Örjan”. However, “Orjan” and “Örjan” get different encodings – ARJN vs RJN. Why is that? One look under the hood (the implementation in DoubleMetaphone.java) will give you the answer:

private static final String VOWELS = "AEIOUY";

So the Scandinavian vowels “ö”, “ä”, “å”, “ø” and “æ” are not present. If we just add these then compile and use the new version of the DM implementation we get the desired output – ARJN for both “Örjan” and “Orjan”.

Finally, if you don’t want to use DM or maybe it is really not suitable for your task, you still may use the same principles and create your own encoder by relying on regular expressions for example. Suppose you have a list of bogus product names which are just (mis)spelling variations of some well known names and you want to search for the original name but get back all ludicrous variants. Here is one albeit very naïve way to do it. Given the following names:

CupHoulder

CappHolder

KeepHolder

MacKleena

MackCliiner

MacqQleanAR

Ma’cKcle’an’ar

and with a bunch of regular expressions you can easily encode them as “cphldR” and “mclnR”.

String[] ar = new String[]{"CupHoulder", "CappHolder", "KeepHolder",
"MacKleena", "MackCliiner", "MacqQleanAR", "Ma'cKcle'an'ar"};

for (String a : ar) {
a = a.toLowerCase();
a = a.replaceAll("[ae]r?$", "R");
a = a.replaceAll("[aeoiuy']", "");
a = a.replaceAll("pp+", "p");
a = a.replaceAll("q|k", "c");
a = a.replaceAll("cc+", "c");
System.out.println(a);
}

You can now easily find all the ludicrous spellings of “CupHolder” och “MacCleaner”.

I hope this blogpost gave you some ideas of how you can use phonetic algorithms and their principles in order to better discover names and entities that sound alike but are spelled unlike. At Findwise we have done a number of enhancements to DM in order to make it work better with Swedish, Danish and Norwegian.

References

You can learn more about Double Metaphone from the following article by the creator of the algorithm:
http://drdobbs.com/cpp/184401251?pgno=2

A German phonetic algorithm is the Kölner Phonetik:
http://de.wikipedia.org/wiki/Kölner_Phonetik

And SfinxBis is a phonetic algorithm based on Soundex and is Swedish specific:
http://www.swami.se/projekt/sfinxbis.68.html

Enterprise Search and Findability Survey

A few days ago we launched the “Enterprise Search and Findability Survey“. The survey closes at the end of March.

If you complete the survey you will get the report when it  is finished.

[DKB url=”http://svy.mk/xJz2DM” text=”Take me to the Survey!” title=”The Survey” type=”large” style=”” color=”orange” height=”” width=”” opennewwindow=”no” nofollow=”” textcolor=”#ffffff”]

The survey is for people who are responsible for search in their organisations. If you are a search manager, intranet manager, product owner of search, search editor, in-house developer for search, this survey is for you!

The survey aims to help you by finding out your views about Enterprise Search and Findability. The research will help show what business value an Enterprise Search solution can provide.

The survey is structured into five sections, each of which provides a specific perspective on Findability:
• Business
• Organisation
• User
• Information
• Search Technology

More information about the perspectives is provided in each section.

The survey will take approximately 20-30 minutes of your time. If you need a break, you can continue answering the survey at the same question where you left. If you give us your contact information we will send you the finished report based on this survey when it is finished, we are aiming to have it finished by the month of June.

The survey results will be presented at Enterprise Search Europe 2012 (London, 30-31 May 2012) and Enterprise Search Summit (New York, 15-16 May 2012).

Search and Accessibility

Västra Götalands regionen has introduced a new search solution that Findwise created together with Netrelations. Where both search and accessibility is important. We have also blogged about it earlier (see How to create better search – VGR leads the way). One important part of the creation of this solution was to create an interface that is accessible to everyone.

Today the web offers access to information and interaction for people around the world. But many sites today have barriers that make it difficult, and sometimes even impossible for people with different disabilities to navigate and interact with the site. It is important to design for accessibility  – so that no one is excluded because of their disabilities.

Web accessibility means that people with disabilities can perceive, understand, navigate, interact and contribute to the Web. But web accessibility is not only for people that use screen readers, as is often portrayed. It is also for people with just poor eyesight who need to increase the text size or for people with cognitive disabilities (or sometimes even for those without disabilities). Web accessibility can benefit people without disabilities, such as when using a slow Internet connection, using a mobile phone to access the web or when someone is having a broken arm. Even such a thing as using a web browser without javascript because of company policy can be a disability on the web and should be considered when designing websites.

So how do you build accessible websites?

One of the easiest things is to make sure that the xhtml validates. This means that the code is correct, adheres to the latest standard from W3C (World Wide Web Consortium) and that the code is semantically correct i.e. that the different parts of the website use the correct html ”tags” and in the correct context. For example that the most important heading of a page is marked up with ”h1” and that the second most important is ”h2” (among other things important when making websites accessible for people using screen readers).

It is also important that a site can easily be navigated only by keyboard, so that people who cannot use a mouse still can access the site. Here it is important to test in which order the different elements of the web page is selected when using the keyboard to navigate through the page. One thing that is often overlooked is that a site often is inaccessible for people with cognitive disabilities because the site contains content that uses complex words, sentences or structure. By making content less complex and more structured it  will be readable for everyone.

Examples from VGR

In the search application at VGR elements in the interface that use javascript will only be shown if the user has a browser with java script enabled. This will remove any situations where elements do not do anything because java script is turned off. The interface will still be usable, but you will not get all functionality. The VGR search solution also works well with only the keyboard, and there is a handy link that takes the user directly to the results. This way the user can skip unwanted information and navigation.

How is accessibility related to findability?

http://www.flickr.com/photos/morville/4274260576/in/set-72157623208480316/

Search and Accessibility

Accessibility is important for findability because it is about making search solutions accessible and usable for everyone. The need to find information is not less important if you are blind,  if you have a broken arm or if you have dyslexia. If you cannot use a search interface you cannot find the information you need.

“what you find changes who you become” -Peter Morville

In his book Search Patterns Peter Morville visualizes this in the ”user experience honeycomb”. As can been seen in the picture accessibility is as much a part of the user experience as usability or findability is and a search solution will be less usable without any of them.

High Expectations to Googlify the Company = Findability Problem?

It is not a coincidence that the verb “to google” has been added to several renowned dictionaries, such as those from Oxford and Merriam-Webster. Search has been the de facto gateway to the Web for some years now. But when employees turn to Google on the Web to find information about the company they work for, your alarm bells should be ringing. Do you have a Findability problem within the firewall?

The Google Effect on User Expectations

“Give us something like Google or better.”

 

“Compared to Google, our Intranet search is almost unusable.”

 

“Most of the time it is easier to find enterprise information by using Google.”

The citations above come from a study Findwise conducted during 2008-2009 for a customer, who was on the verge of taking the first steps towards a real Enterprise Search application. The old Intranet search tool had become obsolete, providing access to a limited set of information sources only and ranking outdated information over the relevant documents that were in fact available. To put it short, search was causing frustration and lots of it.

However, the executives at this company were wise enough to act on the problem. The goal was set pretty high: Everybody should be able to find the corporate information they need faster and more accurately than before. To accomplish this, an extensive Enterprise Search project was launched.

This is where the contradiction comes into play. Today users are so accustomed to using search as the main gateway to the Web, that the look and feel of Google is often seen as equal to the type of information access solution you need behind the firewall as well. The reasons are obvious; on the Web, Google is fast and it is relevant. But can you—and more importantly should you—without question adopt a solution from the Web within the firewall as well?

Enterprise Search and Web Search are different

  1. Within the firewall, information is stored in various proprietary information systems, databases and applications, on various file shares, in a myriad of formats and with sophisticated security and version control issues to take into account. On the Web, what your web crawler can find is what it indexes.
  2. Within the firewall, you know every single logged in user, the main information access needs she has, the people she knows, the projects she is taking part in and the documents she has written. On the Web, you have less precise knowledge about the context the user is in.
  3. Within the firewall, you have less links and other clear inter-document dependencies that you can use for ranking search results. On the Web, everything is linked together providing an excellent starting point for algorithms such as Google’s PageRank.

Clearly, the settings differ as do user needs. Therefore, the internal search application will be different from a search service on the web; at least if you want it to really work as intended.

Start by Setting up a Findability Strategy

When you know where you are and where you want to be in terms of Findability—i.e. when you have a Findability strategy—you can design and implement your search solution using the search platform that best fits the needs of your company. It might well be Google’s Search Appliance. Just do not forget, the GSA is a totally different beast compared to the Google your users are accustomed to on the Web!

References

http://en.wikipedia.org/wiki/Googling

Six Simple Steps to Superior Search

Do you have your search application up and running but it still doesn’t quite seem to do the trick? Here are six simple steps to boost the search experience.

Avoid the Garbage in-Garbage out Syndrome

Fact 1: A search application is only as good as the content it makes findable

If you have a news search service that only provides yesterday’s news, the search bit does not add any value to your offering.

If your Intranet search service provides access to a catalog of employee competencies, but this catalog does not cover all co-workers or contain updated contact details, then search is not the means it should be to help users get in touch with the right people.

If your search service gives access to a lot of different versions of the same document and there is no metadata available as to single out which copy is the official one, then users might end up spending unnecessary time reviewing irrelevant search results. And still you cannot rule out the risk that they end up using old or even flawed versions of documents.

The key learning here is that there is no plug and play when it comes to accurate and well thought out information access. Sure, you can make everything findable by default. But you will annoy your users while doing so unless you take a moment and review your data.

Focus on Frequent Queries

Fact 2: Users tend to search for the same things over and over again.

It is not unusual that 20 % of the full query volume is made up of less than 1 % of all query strings. In other words, people tend to use search for a rather fixed set of simple information access tasks over and over again. Typical tasks include finding the front page of a site or application on the Intranet, finding the lunch menu at the company canteen or finding the telephone number to the company helpdesk.

In other words, you will be much advised to make sure your search application works for these highly frequent (often naïve) information access tasks. An efficient way of doing so is to keep an analytic eye on the log file of your search application and take appropriate action on frequent queries that do not return any results whatsoever or return weird or unexpected results.

The key learning here is that you should focus on providing relevant results for frequent queries. This is the least expensive way to get boosted benefit from your search application.

Make the Information People Often Need Searchable

Fact 3: Users do not know what information is available through search.

Users often believe that a search application gives them access to information that really isn’t available through search. Say your users are frequently searching for ”lunch menu”, ”canteen” and ”today’s lunch”, what do you do if you do not have the menu available at all on your Intranet or Web site?

In the best of worlds, you will make frequently requested information available through search. In other words, you would add the lunch menu to your site and make it searchable. If that is not an option, you might consider informing your users that the lunch menu—or some other popular information people tend to request—is not available in the search application and provide them with a hard-coded link to the canteen contractor or some other related service as a so called “best bet” (or sponsored link as in Google web search).

The key learning here is to monitor what users frequently search for and make sure the search application can tackle user expectations properly.

Adapt to the User’s Language

Fact 4: Users do not know your company jargon.

People describe things using different words. Users are regularly searching for terms which are synonymous to—but not the same as—the terms used in the content being searched. Say your users are frequently looking for a ”travel expense form” on your Intranet search service, but the term used in your official company jargon  is ”travel expenses template”. In cases like this you can build a glossary of synonyms mapping those common language terms people tend to search for frequently to official company terms in order to satisfy your users’ frequent information needs better without having to deviate from company terminology. Another way of handling the problem is to provide hand-crafted best bets (or sponsored links as in Google web search) that are triggered by certain common search terms.

Furthermore, research suggests that Intranet searches often contain company-specific abbreviations. A study of the query log of a search installation at one of Findwise’s customers showed that abbreviations—query strings consisting of two, three or four letters—stood for as much as 18 % of all queries. In other words, it might be worthwhile for the search application to add the spelled-out form to a query for a frequently used abbreviation. Users searching for “cp” on the Intranet would for example in effect see the results of the query “cp OR collaboration portal”

The lesson to learn here is that you should use your query log to learn the terminology the users are using and adapt the search application accordingly, not the other way around!

Help Users With Spelling

Fact 5: Users do not know how to spell.

Users make spelling mistakes—lots of them. Research suggests that 10—25 % of all queries sent to a search engine contain spelling mistakes. So turn on spellchecking in your search platform if you haven’t already! And while you are at it, make sure your search platform can handle queries containing inflected forms (e.g. “menu”, “menus”, “menu’s”, “menus’”). There’s your quick wins to boost the search experience.

Keep Your Search Solution Up-To-Date

Fact 6: Your search application requires maintenance.

Information sources change, so should your search application. There is a fairly widespread misconception that a search application will maintain itself once you’ve got it up and running. The truth is you need to monitor and maintain your search solution as any other business-critical IT application.

A real-life example is a fairly large enterprise that decided to perform a total makeover of its internal communication process, shifting focus from the old Intranet, which was built on a web content management system, in favor of a more “Enterprise 2.0 approach” using a collaboration platform for active projects and daily communication and a document management system for closed projects and archived information.

The shift had many advantages, but it was a disaster for the Enterprise Search application that was only monitoring the old Intranet being phased out. Employees looking for information using the search tool would in other words only find outdated information.

The lesson to learn here is that the fairly large investment in efficient Findability requires maintenance in order for the search application to meet the requirements posed on it now and in the future.

References

100 Most Often Mispelled Misspelled Words in English – http://www.yourdictionary.com/library/misspelled.html

Definition of “sponsored link” – http://encyclopedia2.thefreedictionary.com/Sponsored+link