1
$\begingroup$

I want to implement fast text-search over a Rope data structure. That is, a B-Tree of characters, where the characters are not sorted. (Meaning the standard way to search in a B-Tree by key does not apply.) This data structure is good for making incoherent edits to, but retrieving the character at a given index takes $O(\log n)$ time. All the text search algorithms I've examined so far seem to assume that accessing characters in $O(1)$ and therefore tend to use a lot of accesses. In particular, the search algorithm I've implemented is performing poorly on large files, (hundreds of thousands of characters.) Profiling reveals most of the time to be spent in retrieving the characters to be compared.

The particular algorithm I currently have implemented is the Two-way string-matching algorithm. I chose it for my first attempt mainly because it needs only $O(1)$ additional memory, and not having an additional data structure to implement seemed like it would speed up implementation.

So, I'm wondering are there any well-described search algorithms exist which are designed for use on a B-Tree, or which otherwise perform well in such an environment? I assume the algorithms I have been looking at are trying to minimize comparisons, which I suppose would tend to minimize character retrieval as well. Does it seems sensible to suppose that one would design an algorithm differently if it was to be used on a data structure with a larger than $O(1)$ indexing time?

$\endgroup$
  • $\begingroup$ What is the size of your search patterns? $\endgroup$ – Dmitri Urbanowicz Apr 16 at 11:19
  • $\begingroup$ Typically very small relative to the text to be searched. $\endgroup$ – Ryan1729 Apr 16 at 11:20
1
$\begingroup$

Rooted trees, balanced or not, can be traversed in linear time via depth-first search. Actual implementations of balanced trees usually provide a way to iterate through it, taking amortized $O(1)$ for each step. So any algorithm will work without $O(\log n)$ overhead if it makes only a single pass through the string (or if it only requires a small bounded sliding window).

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I’m using a rope implementation from a library, and the documentation claims amortized $O(1)$ and worse case $O(\log n)$. Measured performance on searching small ropes is great, but I get a significant drop on sufficiently large ropes. I would like to be able to handle searching large and I am wondering if I have reasonable options there. $\endgroup$ – Ryan1729 Apr 16 at 11:41
  • 1
    $\begingroup$ If the library implementation can't go from the first character to the last one within the timeframe you want, I think there's nothing you can do. $\endgroup$ – Dmitri Urbanowicz Apr 16 at 11:47

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.