2

I've noticed that text editors and such have a more-than-prefix/suffix-based pattern matching algorithm going on behind the scenes. And StackOverflow's tag matching algorithm does more than just prefix/suffix matching:

enter image description here

I am wondering what (one of the possibly many sorts) of data structures are required to implement this sort of feature. I have been reading about tries, but they seem to be better at prefix matching, and I'm not quite sure exactly the type of matching going on on the SO tags autocomplete. However, looking at autocomplete implementation recommendations usually suggests tries.

Wondering if one could briefly outline how it is done. Knowing even what the data structures or types of algorithms are called would help better search for the details.

This is for relatively small strings of say less than 1000 characters or perhaps less than 200 if it makes a bigger difference.

Improve this question
2
  • 3
    You might want to use your favourite search engine with phrases - "fuzzy matching" or "approximate string matching".
    – rsm
    Jul 20, 2018 at 13:28
  • @rsm fuzzy match is relevant when not all the letters in the pattern are expected in the match (or not consecutively in the right order). While this is an interesting thought (and usually involves some "editin distance"), this seems not to correspond to the example of the question: doesn't the SO search look for all the letters of the pattern to appear in the right order in the potential tags ?
    – Christophe
    Jul 23, 2018 at 10:09

1 Answer 1

Reset to default
-1

You're example looks for exact matches of a single pattern made of successive characters.

If your text items are in memory, a quick approach would be to use a fast string search using for example Boyer-Moore search or its variants, to find the suitable items. The longer the pattern, the more efficient it gets.

If your text items are on disk, you'd better use full text indexing. Your example is about partial matches in elementary tokens (i.e. words: a tag is one word only). If your database support advanced text indexing functions, just use them (e.g. MongoDB, PostgreSql, SAP Hana). But if not, an easy alternative could be to build an index of individual words/tokens, that maps words to all the text items in which they occur (many to many relationship). Your autocompletion problem would then be reduced to :

  • Finding all the words in the dictionary that match the substring.
  • Whenever characters are added to the pattern, you just eliminate the wrong matches.
  • Of course, finding the right text items is not sufficient: you'd still need to display these entries and highlight the relevant part: here comes Boyer-More again.
Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.