Algorithm for autocomplete?

by

For (heh) awesome fuzzy/partial string matching algorithms, check out Damn Cool Algorithms:

These don’t replace tries, but rather prevent brute-force lookups in tries – which is still a huge win. Next, you probably want a way to bound the size of the trie:

  • keep a trie of recent/top N words used globally;
  • for each user, keep a trie of recent/top N words for that user.

Finally, you want to prevent lookups whenever possible…

  • cache lookup results: if the user clicks through on any search results, you can serve those very quickly and then asynchronously fetch the full partial/fuzzy lookup.
  • precompute lookup results: if the user has typed “appl”, they are likely to continue with “apple”, “apply”.
  • prefetch data: for instance, a web app can send a smaller set of results to the browser, small enough to make brute-force searching in JS viable.

More Related Contents:

  1. How to create the most compact mapping n → isprime(n) up to a limit N?
  2. Reverse the ordering of words in a string
  3. Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations
  4. Data structures for loaded dice?
  5. Find kth smallest element in a binary search tree in Optimum way
  6. How to implement a queue using two stacks?
  7. How do you validate a binary search tree?
  8. design a stack such that getMinimum( ) should be O(1)
  9. Computing set intersection in linear time?
  10. Best algorithm to test if a linked list has a cycle
  11. How to delete in a heap data structure?
  12. What is the difference between tree depth and height?
  13. How Do I Choose Between a Hash Table and a Trie (Prefix Tree)?
  14. O(klogk) time algorithm to find kth smallest element from a binary heap
  15. In Order Successor in Binary Search Tree
  16. Skip List vs. Binary Search Tree
  17. Hashing a Tree Structure
  18. graph – Dijkstra for The Single-Source Longest Path
  19. How can I return an array of struct in solidity?
  20. The intersection of all combinations of n sets
  21. Why increase pointer by two while finding loop in linked list, why not 3,4,5?
  22. Why use binary search if there’s ternary search?
  23. Why are hash table expansions usually done by doubling the size?
  24. Algorithm for merging two max heaps?
  25. What are probabilistic data structures?
  26. How to find the number of different shortest paths between two vertices, in directed graph and with linear-time?
  27. Why is vector array doubled?
  28. Given a set of intervals, find the interval which has the maximum number of intersections
  29. Can brute force algorithms scale?
  30. How to apply binary search O(log n) on a sorted linked list?

Leave a Comment