5 ms·

A query that matches phrase prefixes - for example "Epic w" will match both "Epic win" and "Epic wonder". This is particularly useful for implementing Google In

• sigil 16y ago
  I was curious how they implemented prefix matching, so I went and looked at the code [1]. Unfortunately, this is just a simple linear scan that calls .startswith(). It is possible to do fast (log N) prefix matching with radix / critbit trees. [1] https://github.com/Greplin/greplin-lucene-utils/blob/master/src/main/java/com/greplin/lucene/query/PhrasePrefixQuery.java https://github.com/Greplin/greplin-lucene-utils/blob/master/...
  • nostrademons 16y ago
    Radix trees are O(k), where k is the length of the query string. Anyway, for prefix matching, you want to take careful note of the size and shape of your data, because it matters for which algorithm is fastest. If your data all fits in RAM (or better yet, all fits in L2 cache), then I've had very good results with binary search (O(log N)) to find the first matching result, and then linear scan to find all possible suffixes. This is a lot more cache-friendly than radix trees, which have better theoretical performance but often touch memory that's all over the place.
    • sigil 16y ago
      > Radix trees are O(k) Yes, thank you.
• techtalsky 16y ago
  Luckily it does exist in Solr in the form of prefixed term queries. I'm surprised to find out it's not in vanilla Lucene.