Map Index Random Help Topics

## Topic: string operations

topics > computer science > data > Group: sequence operations

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)

Updated barberCB 2/05