Quote: algorithms for string search and sort; radix quicksort and ternary search trees [»bentJL1_1997]

Quote: back-tracking is rarely a problem so KMP search is similar to naive search for most files [»fenwP7_2001]

Quote: average case for 2 string matching algorithms, Boyer-Moore-Horspool faster than hardware character match for most pattern lengths [»baezRA8_1989]

Quote: Boyer and Moore's string matching algorithm is more efficient than Knuth et al and Karp and Rabin [»daviG6_1986]

Quote: speed up the Boyer-Moore and reverse factor algorithms by remembering the last matched segment; for binary alphabets Turbo_RF is fastest [»crocM10_1994]

Quote: using a pattern shift table, can search for substrings faster than the Boyer-Moore algorithm [»sundDM8_1990]

Quote: fast string searching by variants of Boyer-Moore; toolkit for skip loop, match and shift components [»humeA11_1991]

Quote: Boyer-Moore string matching requires roughly 3n comparisons and less than 4n comparisons [»coleR10_1994]

Quote: simple code for an efficient version of Boyer-Moore-Horspool string matching algorithm [»baezRA8_1989]

Quote: string-matching variant combines Knuth-Morris-Pratt (fewer comparisons) and Boyer-Moore-Horspool (better in worst case and preprocessing)

Quote: sublinear search algorithm for regular expressions on preprocessed text; uses a Patricia tree for the index [»baezRA11_1996]

Quote: identify search records by shortest-substrings of regular expressions; e.g., all blocks [»clarCL5_1997]

Quote: the leftmost longest match rule does not work for regular expressions in structured text [»clarCL5_1997]

Quote: use the leftmost shortest match rule for regular expressions in structured text without predefined retrieval units [»clarCL5_1997]

Quote: skip text runs during regular expression searching by recognizing shorter, reverse prefixes; performance similar to DFA [»navaG7_1999]

Quote: first solution for regular expression searching in compressed text; faster than decompression plus search [»navaG7_2001]

Quote: compared longest match search for Ziv-Lempel compression; lists for each character, best overall [»bellT7_1993]

Quote: a maximal repeating pattern is as long as possible or occurs independently; use position trees for quadratic algorithm [»siocAC10_1991]

Quote: for patterns that fit in a computer word, fast, bit-parallel string matching based on the Shift-Or algorithm; optimal average and worst case running times; variation for Shift-Add algorithm and Hamming distance [»fredK11_2005]

Quote: use diagrams, filters, and preprocessing for fast, frequent searches; much faster with initialization overhead of 5-10 conventional searches [»fenwP7_2001]

Quote: the right mouse button indicates arguments to a generalized search facility that locates files, file locations, and text [»pikeR1_1994]

Quote: constant-time insertion and find-min for priority queues; black box trades delete time for insert time [»alstS7_2005]

Quote: simple, optimal, external sort using sampling and a priority queue; exactly two reads and writes per record [»leuFC2_2000]

Quote: skip quadtrees and octrees for multi-dimensional data; efficient insert, delete, location, approximate range, approximate nearest neighbor; logarithmic-height search and update [»eppsD6_2005]

Quote: a retrieval in a splay tree moves the retrieved node to the root, halves the length of the access path, and slightly increases other access paths [»tarjRE3_1987]

Quote: conjecture that splay trees are optimal for binary search under amortized costs [»tarjRE3_1987]

Quote: a median split tree is a balanced tree with the most frequent key at the root [»shelBA11_1978]

Quote: self-adjusting algorithm for searching a linear dictionary list; online, fast successful and unsuccessful search, two extra bits per key [»huiLC11_1993]

Quote: self-adjusting binary search trees are slower than AVL or binary trees; by CPU time, binary trees are often best [»bellJ4_1993]

Quote: ternary search trees better than binary trees, tries, and hashing; dynamic, fast operations including unsuccessful search and sort [»bentJ4_1998]

Quote: randomized binary search trees based on size of subtrees; O(log n); access by rank [»martC3_1998]

Quote: with suffix trie, search time independent of text length [»nelsMR8_1996]

Quote: use compressed suffix arrays and trees to search for short strings in O(1) time with O(n) space [»grosR5_2000]

Quote: simple, space efficient suffix trees using balanced parentheses; O(n lg n) space and O(m) search [»munrJI5_2001]

Quote: skip list of nodes with k forwarding pointers; levels chosen randomly then never changes; simple updates [»pughW6_1990]

Quote: skip list is a randomized data structure for balanced trees; simple and space efficient (1.5 pointers per node) [»pughW6_1990]

Quote: skip quadtrees and octrees for multi-dimensional data; efficient insert, delete, location, approximate range, approximate nearest neighbor; logarithmic-height search and update [»eppsD6_2005]

Quote: Burrows Wheeler Transform reversibly reorders data; models data by the string following a character [»nelsMR9_1996]

Quote: use Burrows-Wheeler block-sorted data for dynamic searching; compressed, rapid searches; groups similar substrings together [»willK12_2003]

Quote: for search, speed and character comparisons may not be related; e.g., diagram search is 386x better by comparisons and 240x to 13x better by speed [»fenwP7_2001a]