Which search is faster, binary search, or using the prefix tree?

Question

Suppose I have a list of lines and a tree of prefixes for these lines, and I would like to find a line with a key, which one is faster? search binary search or prefix?

Why and what is the time complexity?

Thanks!

Answer 1

Both methods have their advantages and disadvantages:

Suffix tree

• Benefits:
  • O (N) construction complexity.
  • O (M) search for a pattern of length M
  • They allow online construction
• Disadvantages:
  • Inefficient space
  • Truly sophisticated construction algorithms

Binary Search (with suffix)

• Benefits:
  • You can sort an array of strings in O (N) time
  • Effective space (five times less memory (at least))
  • Simple and simple construction algorithms
• Disadvantages:
  • They do not support online construction.
  • O (M lg N) time to search for a pattern of length M among N lines (this can be reduced to O (M + lg N), but it is still a bit slower than the suffix tree)

Both of these data structures are really powerful. If your application requires a quick search, but enough space, be sure to specify the suffix trees. But if space matters, then the suffix array (binary search) is the only choice you have ...