Open Ended Search Problem

Disclaimer: It is a made up problem. Not to be attempted by light hearted.

Problem:
I have a 300 word text. I have a large list of indexed strings (Length of string ~ 20, Number of strings ~ 1M). I need to figure out phrases in the 300 word text that match exactly to one of the strings in the large list of strings I have.

A naive approach:
Taking all 45000 (300 C 2) phrases, search in the large list of strings. Can we do better than this? We need to minimize calls to list of indexed strings!


Comments

  1. Nim12:23 PM, May 31, 2014

    approach 1: Compute Hash values of all 300 texts, run any string matching algo with that and the list of strings you have such that only if the hash values match, comparison is made.

    approach 2: If no memory constraints, then run counting sort on the 300 words, and use binary search. Or create 300X300 matrix and run binary search on the 2D matrix. That will will complexity o(log(300square))

    ReplyDelete
  2. Unknown2:29 PM, September 16, 2017

    We can make trie using 20 length word window size (20 length window will traverse over the entire 300 word text). Then we can traverse the list and search for strings in the trie.

    ReplyDelete
    Replies
    1. Pratik Poddar11:21 AM, October 23, 2026

      Hashing helps the constant factor but the structure to reach for here is Aho-Corasick: build the automaton over the 1M dictionary strings ONCE (they are the fixed, indexed side), then stream the 300-word text through it in O(text length + matches) - every matching phrase found in a single pass, no per-phrase lookups at all. That beats both the 45,000-phrase probing and per-phrase binary search. (replied using AI)

      Delete
    2. Pratik Poddar1:50 PM, October 23, 2026

      You have the automaton on the wrong side: the dictionary is the large static set, so build the trie/Aho-Corasick machine over the 1M strings and feed the TEXT through it. Your version pays O(text) construction but then O(20) per dictionary string per lookup - reversed economics. With AC over the dictionary: one pass, O(300 words + number of matches). (replied using AI)

      Delete

Post a Comment

Popular posts from this blog

Lion and Man in a Circular Cage: Can the Lion Catch the Tamer?

Source: Asked to me by Pramod Ganapathi (PhD Student at Stony Brook University) Problem: A lion and a lion tamer are enclosed within a circular cage. If they move at the same speed but are both restricted by the cage, can the lion catch the lion tamer? (Represent the cage by a circle, and the lion and lion tamer as two point masses within it.) Solution: Highlight the part between the * symbols for the answer. * Answer: surprisingly, no - the tamer can avoid being caught forever. This is the famous Lion and Man problem, posed in the 1930s and settled by Besicovitch; the proof appears in Littlewood's "A Mathematician's Miscellany" (and opens Bollobas's "The Art of Mathematics"). What the lion CAN do (Rado's strategy): move to the center, then always stay on the radius through the tamer, using any spare speed to move outward. Since the lion runs on a smaller circle, it can match the tamer's angular position while steadily increasing its radiu...
Read more

Polya's Urn Problem: Expected Balls in the Smaller Urn

Puzzle: There are two urns with one ball each. Each of subsequent n-2 balls is placed into one of these urns, with probability proportional to the number of balls already in that urn. What is the expected number of balls in the smaller sized urn? Source: P. Winkler's Puzzles book. (Chapter: Probability). Solution: Highlight the part between the * symbols for the answer. * This problem can be reformulated as the following problem. Suppose I have a stack of black cards and one red card. Initially I take red card in my hand. Now I add black cards randomly between any two cards (so, initially its either above or below red). Note that the probability that I add the card above the red card, when x-1 is the number of cards above red and y-1 is the number of cards below red is x/(x+y). Let the problem be if red card is dividing the black cards into two sets, what is the expected number of black cards in the smaller section. So, we see that the two problems are equivalent. No...
Read more

Expected Tosses for Consecutive Heads: 2 Heads vs 3 Heads Puzzle

Let's say A keep tossing a fair coin, until he get 2 consecutive heads, define X to be the number of tosses for this process; B keep tossing another fair coin, until he get 3 consecutive heads, define Y to be the number of the tosses for this process. 1) Calculate P{X>Y} 2) What's the expected value of X 3) What's the expected value of Y This is probably the hardest puzzle I have ever put on my blog. Hence, I will post its solution in the post directly rather than on comment. Solution: 1) (Solved by me finally after 13 months :)) Make a state diagram. Let the state be (a,b) where a is the number of consecutive heads streak "A" is on currently and b is the number of consecutive heads streak "B" is on currently. So, (0,3) (1,3) are final accepted states and (2,0) (2,1) (2,2) (2,3) are failure states. If you get tails, your contribution to the state reaches to "0" f(State) = P(X>Y | "State" configuration initially) ...
Read more