“For bonus points make the test partial/fuzzy. e.g. entering zimb will result in Zimbabwe
:)”
This was part of the assessment that got me a job with Lunatech, working on Audi's platform. I'm starting there now. The brief asked for a query page and reports in a web application over three CSV files containing countries, airports and runways.
The main query takes a country name or code and shows its airports and runways. I'm more interested in the bonus. What if somebody stops halfway through a name? Or remembers it but can't quite spell it? Half a name, a nearly remembered spelling.
“Partial/fuzzy” leaves me a lot to decide, it comes with a smiley though.
This part was fun. I'd recently learnt about search while working on Sound of Jersey, and I got to use that knowledge for something else. Country names gave me a different set of things to try it on. I built it with Spring Boot and an in-memory database. At startup it loads countries before airports and airports before runways and builds the search index, so the search has the data ready when I ask it a question.
What counts as close enough?
zimb is the start of Zimbabwe, while zimbabew has the ending wrong. ZW is a country code and cote d'ivoire leaves out the accent.
In my mind these are four different things somebody might be asking the search to do. Someone typing zimb may have stopped before finishing the name, and treating it as a misspelt complete word answers the wrong question before they've had a chance to finish it.
The code has three indexed forms and the name has three more, all six fields get searched, and the answer is still one country.
I got quite involved in this bonus sentence.
The word analyser comes from Sound of Jersey, where I've used it to make a nearly remembered band name easier to find. Bringing it here lets me ask what a country name needs that a band name didn't. It normalises text and includes a sound-alike code. The site tour follows its stages. Searching only those word fields puts Zambia first for zimb, which is a perfectly good country, but it isn't helping me collect these particular bonus points. A partly typed name needs more than the complete-word treatment.
The second form stores prefixes, called edge n-grams. For Zimbabwe, they begin like this:
zim
zimb
zimba
zimbab
zimbabw
zimbabwe
So zimb is already in the index. I like how direct that is, we can match it without waiting for somebody to finish typing Zimbabwe, and those extra beginnings give me something the bonus actually asks for.
The third form stores short pieces from anywhere within a word, n-grams of three to five characters. A middle section such as imba can survive even when the end of the input is wrong. I'm hoping those pieces will help with nearly remembered names. Unrelated names can share them too. The app only opens one country's page so the first match matters.
Which field is doing the work?
The request uses Hibernate Search's phrase-query builder across all six fields. It allows a slop of three for token positions in a phrase. Allowing three misspelt characters is another thing entirely.
The word fields receive a boost of two when indexed, giving their evidence more weight in scoring because I don't want a shared fragment to count as heavily as a good word match. The application takes the highest-ranked country and uses it to load the results page.
My analysers process the query as well as the stored names. Zimbabwe comes back for zimbabew. Which field deserves the credit? I can point to the shared pieces, or rather to one possible reason for the match. The query goes through the prefix analyser too and several beginnings match before the wrong ending enters the picture.
Removing the n-gram fields doesn't make this query fail. Prefixes still help. Even the word analyser finds Zimbabwe in this case.
I can't give each technique its own spelling mistake and pretend the others politely stay out of the way.
Here are the first results for the full query over the supplied country data:
| Input | First result |
|---|---|
zimb | Zimbabwe |
zimbabew | Zimbabwe |
ZW | Zimbabwe |
cote d'ivoire | Côte d'Ivoire |
zam | Zambia |
reunion | Réunion |
qqqzzzx | No result |
Take some fields away. For zimb, prefixes alone put Zimbabwe first, short pieces alone put Zimbabwe first, and now I've got a reason for both representations beyond the fact that the full query happens to work.
Then there's ZW. Two characters. Both kinds of n-gram start at three, so neither produces useful query tokens for the code and neither returns a country on its own. That's a job for the word fields.
Why that country? That's what I'm trying to understand by taking fields away. Zimbabwe at the top is encouraging, knowing why Zambia gets there under another query tells me more about what I've built.
For zimb, the answer is now Zimbabwe.
And the assessment has done its other job. I'm moving to the Netherlands to start with Lunatech, and I'm excited. It feels like the beginning of a new life.