Group:
algorithms
Topic:
approximate string matching and pattern matching with errors
Topic:
boolean values, binary numbers, and bit strings
Topic:
pattern matching
Topic:
processing a sequence
Topic:
search algorithms
Topic:
sort algorithms
Topic:
strings
Topic:
string and list concatenation
Topic:
string transformation languages
Topic:
sub-sequences
| |
Summary
Many operations have been defined for strings including: compare, concatenate, count, delete components, delimitate tokens, deque from end, edit, enque, head, insert, limit length, membership, merge, ordered insertion, permute, predecessor, repeat, replace, restructure, rotate left or right, shift left or right, sort, sub-string, successor, tail, test for null. Most operations use finite length strings. A number of languages exist primarily for string operations. (cbb 5/80)
Subtopic: external memory operation 
| Quote: survey of external memory algorithms; includes sorting, permuting, FFT, graphs, databases, GIS, text processing [»vittJS6_2001]
|
Subtopic: shortest edit distance
| Quote: algorithms for the shortest edit sequence for converting between two strings [»tichWF11_1984]
| | Quote: algorithm for string-to-string correction problem using edit operations; time proportional to the product of the string lengths [»wagnRA1_1974]
|
Subtopic: longest common subsequence, LCS
| Quote: a fast and practical bit-vector algorithm for length of longest common subsequence [»crocM12_2001]
| | Quote: given length of longest common subsequence (LCS), generate the subsequence using Hirchberg's paradigm [»crocM12_2001]
| | Quote: file differences as a minimal list of line changes; longest common subsequence; linear complexity in practice [»huntJW7_1976]
|
Subtopic: maximal repeating pattern, covering set
| Quote: a maximal repeating pattern is as long as possible or occurs independently; use position trees for quadratic algorithm [»siocAC10_1991]
| | Quote: algorithm for minimal covering set of common substrings
|
Subtopic: concate, repeat, extract
| QuoteRef: schwJT_1973 ;;501 string operations concatenation (+), repetition (*), size (#), extraction (a(1:h) )
|
Subtopic: string rewrite
| QuoteRef: grayJC_1973 ;;169 merge (A '++ B) the blank indices (may be set blank) of A are replaced by corresponding values in B
| | QuoteRef: grayJC_1973 ;;169 restructure (<%) result := new-idem-format <% item by common index names.
| | QuoteRef: mullAP_1964 ;;452 definition by n A n(3)(3)H(1)B(2)C(1)D(3) then can "insert the value string into another, or "join" two named strings together(retain names)
| | QuoteRef: mullAP_1964 ;;452 have set operations on strings, induce structure, edit, count levels, e.g., A count ".circle2." -> B where A is n A n.circle4..circle4.A.circle1.C.circle2.C.circle1.D.circle3 generates n B n.circle1.2.circle2
|
Subtopic: bitvector
| Quote: unidirectional bitvector analysis used for liveness, reaching def, def-use, code motion, partial dead code, and strength reduction; works for parallel programs [»knooJ5_1995]
|
Subtopic: split and join
| QuoteRef: sammJE_1969 ;;427 expand and compression functions on constitutes e.g. The+dog becomes under * $1+$1=//*e1 2* T+h+e+d+o+g and reversed by *$3+$=//*k1,*k2*
|
Subtopic: cursor operation
| Quote: in Icon, use 'move' and 'tab' to move cursor and return the intervening substring [»grisRE4_1980, OK]
|
Subtopic: permute
| QuoteRef: grayJC_1973 ;;169 permute (index-set '% set) e.g., [3 2]'%[a b c d] == [c b]
|
Subtopic: justification
| QuoteRef: seedH_1971 ;;160 string moves both left and right justified
|
Subtopic: examples
| QuoteRef: ledgHF9_1971 ;;136 PANON AXLE: string manipulation
|
Subtopic: cost of string operations
Quote: OS6 profile showed almost all execution time spent in unpacking buffers, testing contents, and storing elsewhere
[»stoyJE3_1972]
|
Related Topics
Group: algorithms (6 topics, 94 quotes)
Topic: approximate string matching and pattern matching with errors (19 items)
Topic: boolean values, binary numbers, and bit strings (44 items)
Topic: pattern matching (42 items)
Topic: processing a sequence (17 items)
Topic: search algorithms (40 items)
Topic: sort algorithms (24 items)
Topic: strings (13 items)
Topic: string and list concatenation (9 items)
Topic: string transformation languages (17 items)
Topic: sub-sequences
(13 items)
|
