Topic: string operations

topics > computer science > data > Group: sequence operations


approximate string matching and pattern matching with errors
boolean values, binary numbers, and bit strings
pattern matching
processing a sequence
search algorithms
sort algorithms
string and list concatenation
string transformation languages


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 up

Quote: survey of external memory algorithms; includes sorting, permuting, FFT, graphs, databases, GIS, text processing [»vittJS6_2001]

Subtopic: shortest edit distance up

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 up

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 up

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 up

QuoteRef: schwJT_1973 ;;501 string operations concatenation (+), repetition (*), size (#), extraction (a(1:h) )

Subtopic: string rewrite up

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 up

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 up

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 up

Quote: in Icon, use 'move' and 'tab' to move cursor and return the intervening substring [»grisRE4_1980, OK]

Subtopic: permute up

QuoteRef: grayJC_1973 ;;169 permute (index-set '% set) e.g., [3 2]'%[a b c d] == [c b]

Subtopic: justification up

QuoteRef: seedH_1971 ;;160 string moves both left and right justified

Subtopic: examples up

QuoteRef: ledgHF9_1971 ;;136 PANON AXLE: string manipulation

Subtopic: cost of string operations up

Quote: OS6 profile showed almost all execution time spent in unpacking buffers, testing contents, and storing elsewhere

Related Topics up

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
Copyright © 2002-2008 by C. Bradford Barber. All rights reserved.
Thesa is a trademark of C. Bradford Barber.