2
$\begingroup$

I'm looking for a solution to search for strings in a large text file. I would like to match strings with as many of those words in close proximity as possible.

For example, if a query is for the string "what is the term for a supreme court justice"

  • "a supreme court justice has lifetime tenure, meaning"
  • "the term of justice in the supreme court is.."

Would be matches in they are in the document being searched.

I'm sure that algorithms for this type of searching already exist, but I don't know what they are called or exactly what it is that I'm looking for.

$\endgroup$
  • 2
    $\begingroup$ See edit-distance $\endgroup$ – D.W. Nov 15 at 2:06
  • $\begingroup$ You could build a "low resolution" inverted index that, given a word, tells you just which blocks of the file contain that word, where the file is broken into blocks of, e.g., 100 words each. At query time, find the intersection of the block lists for each query word. (To handle the issue of nearby words that span block boundaries, you can build 2 such indices: In the first index, block 1 is the first 100 words, block 2 the second 100 words, etc., while in the second index, block 1 is words 50-149, block 2 is words 150-249, etc. Look up queries in both.) $\endgroup$ – j_random_hacker Nov 15 at 12:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.