Algorithm: given very large file of strings, find lines containing substring

Question

I'm not sure if cs.stackexchange.com is correct place to ask this question but it looks like most relevant.

On the job interview I was asked a question: lets say we have a very large file, containing a lot of lines with strings. And lets say that one line is a "document". We are building service which takes some string as input and returns numbers of documents containing this string or substring. Which approach would you use?

And I'm stuck with event trying to find a way to do it. Obviously we can just go through the file with every query and count lines containing substring and it will take O(n) time. But there should be more elegant and fast way to do it, right? I have no CS grad, so my knowledge about algorithms and data structures are not systematic.

My intuition says that it should some very basic question (like knackpack problem, for example) and I just don't know right data structure and algorithm to handle it.

It looks like suffix tree could help somehow but I can't find a way - how? Or, maybe, there is some another approach?

Answer 1

You can construct a suffix tree for that very large file and once generated the same can be used for querying.
For Suffix tree generation use Suffix Array approach, there are many algorithm to generate suffix array.
This is a taxonomy of many suffix array algorithm available today
http://www.cas.mcmaster.ca/~bill/best/algorithms/07Taxonomy.pdf

To starts with I would recommend prefix-doubling which required O(n log(n)) time.
You can then look at DC3 which does the job in O(n) time.

Answer 2

Let $\{D_1, D_2, \ldots D_m \}$ be the set of lines (documents) in your problem. Here is a standard solution using a suffix tree.

Build the suffix tree of the string $S = D_1 \$ D_2 \$ \ldots D_n \$$, where $\$$ is a separator character not found in any of your documents.

Suppose your query string is $Q$. Traverse down the suffix tree of $S$ following the characters of $Q$ to find the node (or "locus", to be precise) $v_Q$ corresponding to string $Q$ (if no such node exists, then the string $Q$ does not exist in any of your documents). Walking down the tree takes $O(|Q|)$ time. The leaves in the subtree of $v_Q$ correspond to all suffixes of $S$ that are prefixed by $Q$, so each leaf has the starting position of an occurrence of $Q$ in $S$.

We can add some pointers to the suffix tree so that we can find all leaves in the subtree of a node quickly. For each node, we store the pointer to the leftmost child in the subtree of that node. For each leaf, we store the pointer to the next leaf on the right. This way if node $v_Q$ has $k$ leaves under it, we can iterate those leaves in time $O(k)$.

Now that we have the starting positions of all occurrences, we can find the documents containing the occurrences. An easy way is to precompute an array storing for each position of $S$ the id of the document containing this position. This array makes our data structure functionally similar to a generalized suffix tree, which is just a suffix tree for a set of strings. Your problem could also have been solved by using a generalized suffix tree as a black box.

Summing up, the total time complexity of answering the query is $O(|Q| + k)$, where $k$ is the number of occurrences of $Q$. Barring bit-parallel algoritms, this is the best you can have, because you need to at least read the query, and you need to at least list all the documents containing $Q$.

If the total size of your documents is really large, you might want to look into compressed text indices. There exist compressed representations of suffix trees that take less space, but the query time is slower as a trade-off. Burrows-Wheeler transform based indices can help if the alphabet of your documents is small or the texts are redundant. Compressed text indices that exploit redundancies in your texts are a topic of active research.