Topic: search algorithms

topics > computer science > programming > Group: patterns

information retrieval

adaptive hash table
approximate string matching and pattern matching with errors
collection class
external search and sort
hash table and hash functions
pattern matching
pattern specification
perfect hash table
searching compressed data
sort algorithms
string operations
suffix trie and suffix array

Subtopic: string search/sort up

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)

Subtopic: regular expression search up

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]

Subtopic: longest-match search up

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]

Subtopic: bit-parallel search up

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]

Subtopic: repeated search up

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

Subtopic: search UI up

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

Subtopic: priority queue up

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]

Subtopic: multi-dimensional search up

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]

Subtopic: self-adjusting trees up

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]

Subtopic: binary vs. self-adjusting up

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

Subtopic: ternary search up

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

Subtopic: randomized trees up

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

Subtopic: suffix search up

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]

Subtopic: skip list up

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]

Subtopic: Burrows Wheeler Transform up

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]

Subtopic: benchmarks up

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]

Related Topics up

Group: algorithms   (6 topics, 94 quotes)
Group: information retrieval   (25 topics, 674 quotes)

Topic: adaptive hash table (19 items)
Topic: approximate string matching and pattern matching with errors (19 items)
Topic: b-trees (16 items)
Topic: collection class (11 items)
Topic: external search and sort (23 items)
Topic: hash table and hash functions (41 items)
Topic: pattern matching (42 items)
Topic: pattern specification (15 items)
Topic: perfect hash table (9 items)
Topic: searching compressed data (9 items)
Topic: sort algorithms (24 items)
Topic: string operations (20 items)
Topic: suffix trie and suffix array
(20 items)

Updated barberCB 10/05
Copyright © 2002-2008 by C. Bradford Barber. All rights reserved.
Thesa is a trademark of C. Bradford Barber.