Data Structure for Subsequence Queries
algorithm, data-structures, language-agnostic, search, string
Solution
Tests
There have been four main proposals in this thread:
Shivam Kalra suggested creating an automaton based on all the strings in `A`. This approach has been tried slightly in the literature, normally under the name "Directed Acyclic Subsequence Graph" (DASG).
J Random Hacker suggested extending my 'prefix list' idea to all 'n choose 3' triplets in the query string, and merging them all using a heap.
In the note "Efficient Subsequence Search in Databases" Rohit Jain, Mukesh K. Mohania and Sunil Prabhakar suggest using a Trie structure with some optimizations and recursively search the tree for the query. They also have a suggestion similar to the triplet idea.
Finally there is the 'naive' approach, which wanghq suggested optimizing by storing an index for each element of `A`.
To get a better idea of what's worth putting continued effort into, I have implemented the above four approaches in Python and benchmarked them on two sets of data. The implementations could all be made a couple of magnitudes faster with a well done implementation in C or Java; and I haven't included the optimizations suggested for the 'trie' and 'naive' versions.
Test 1
`A` consists of random paths from my filesystem. `q` are 100 random `[a-z]` strings of average length 7. As the alphabet is large (and Python is slow) I was only able to use duplets for method 3.
Construction times in seconds as a function of `A` size:
Query times in seconds as a function of `A` size:
Test 2
`A` consists of randomly sampled `[a-b]` strings of length 20. `q` are 100 random `[a-b]` strings of average length 7. As the alphabet is small we can use quadlets for method 3.
Construction times in seconds as a function of `A` size:
Query times in seconds as a function of `A` size:
Conclusions
The double logarithmic plot is a bit hard to read, but from the data we can draw the following conclusions:
Automatons are very fast at querying (constant time), however they are impossible to create and store for `|A| >= 256`. It might be possible that a closer analysis could yield a better time/memory balance, or some tricks applicable for the remaining methods.
The dup-/trip-/quadlet method is about twice as fast as my trie implementation and four times as fast as the 'naive' implementation. I used only a linear amount of lists for the merge, instead of `n^3` as suggested by j_random_hacker. It might be possible to tune the method better, but in general it was disappointing.
My trie implementation consistently does better than the naive approach by around a factor of two. By incorporating more preprocessing (like "where are the next 'c's in this subtree") or perhaps merging it with the triplet method, this seems like todays winner.
If you can do with a magnitude less performance, the naive method does comparatively just fine for very little cost.
Problem
In a program I need to efficiently answer queries of the following form: Given a set of strings `A` and a query string `q` return all `s ∈ A` such that q is a subsequence of `s` For example, given `A = {"abcdef", "aaaaaa", "ddca"}` and `q = "acd"` exactly `"abcdef"` should be returned. The following is what I have considered considered so far: For each possible character, make a sorted list of all string/locations where it appears. For querying interleave the lists of the involved characters, and scan through it looking for matches within string boundaries. This would probably be more efficient for words instead of characters, since the limited number of different characters will make the return lists very dense. For each n-prefix `q` might have, store the list of all matching strings. `n` might realistically be close to 3. For query strings longer than that we brute force the initial list. This might speed things up a bit, but one could easily imagine some n-subsequences being present close to all strings in `A`, which means worst case is the same as just brute forcing the entire set. Do you know of any data structures, algorithms or preprocessing tricks which might be helpful for performing the above task efficiently for large `A`s? (My `s`s will be around 100 characters) Update: Some people have suggested using LCS to check if `q` is a subsequence of `s`. I just want to remind that this can be done using a simple function such as: ``` def isSub(q,s): i, j = 0, 0 while i != len(q) and j != len(s): if q[i] == s[j]: i += 1 j += 1 else: j += 1 return i == len(q) ``` Update 2: I've been asked to give more details on the nature of `q`, `A` and its elements. While I'd prefer something that works as generally as possible, I assume `A` will have length around 10^6 and will need to support insertion. The elements `s` will be shorter with an average length of 64. The queries `q` will only be 1 to 20 characters and be used for a live search, so the query "ab" will be sent just before the query "abc". Again, I'd much prefer the solution to use the above as little as possible. Update 3: It has occurred to me, that a data-structure with `O(n^{1-epsilon})` lookups, would allow you to solve OVP / disprove the SETH conjecture. That is probably the reason for our suffering. The only options are then to disprove the conjecture, use approximation, or take advantage of the dataset. I imagine quadlets and tries would do the last in different settings.