文本算法实战：理论与应用深度解析

需积分: 10 119 浏览量更新于2024-07-16 收藏 2.39MB PDF 举报

《文字算法Text Algorithms》是一本深入探讨文本处理算法和数据结构设计的专业书籍，特别关注理论基础与实际应用的结合。书中首先定义了什么是文本，即由一系列字符组成的线性序列，这种数据形式常见于日常的文字处理系统，如word processing软件，用于处理大量字符数据，如本书可能包含超过一百万字符。文本算法在多个学科领域都发挥着重要作用，包括计算机科学、生物学，甚至编程语言的设计中。章节一探讨了高效的文本算法，由M.Crochemore和W.Rytter共同撰写。该章节的焦点在于介绍文本处理的基本概念，比如文本的定义及其在各种应用中的核心地位。文本作为信息的主要载体，是"word processing"系统的核心，这些系统提供了对文本进行编辑、搜索、排序等操作的功能。文本处理涉及的问题，例如字符串匹配、查找、替换等，是理论计算机科学中的重要研究课题，因为它展示了实践与理论的紧密联系。基本的文本问题包括但不限于：查找特定子串（substring search）、模式匹配（pattern matching）、最长公共子序列（longest common subsequence, LCS）以及字符串压缩（string compression），这些问题都是衡量算法效率的关键指标，同时也是设计高效算法和数据结构的基础。解决这类问题不仅需要算法的巧妙设计，还需要考虑时间复杂度和空间复杂度，这是理论计算机科学家们不断追求的目标，以提高处理大规模文本数据的性能。此外，随着生物技术的发展，分子生物学中的DNA序列分析也越来越多地依赖于文本算法。例如，比对不同基因序列、寻找特定变异或寻找相似性，这些任务都需要借助高效的文本处理技术来实现。《文字算法Text Algorithms》这本书为读者提供了深入理解文本处理算法和数据结构的平台，无论是在实际开发中还是理论研究上，都具有很高的价值。它不仅介绍了基本原理，还涵盖了前沿技术和应用案例，适合计算机科学专业的学生、研究人员和工程师参考阅读。

natural numbers, and they synchronously execute the same central program; however, the

action of a given processor depends also on its number (known to the processor). In one step, a

processor can access one memory location. The models differ with respect to simultaneous

access of the same memory location by more than one processor. For the CREW (concurrent

read, exclusive write) variety of PRAM machine any number of processors can read from the

same memory location simultaneously, but write conflicts are not allowed : no two processors

can attempt to write simultaneously into the same location.

Processors

Common Randon Access Memory

120 . . .

1234567

Figure 2.3. A Concurrent Read.

We denote by CRCW (concurrent read, concurrent write) the PRAM model in which, in

addition to concurrent read, write conflicts are allowed : many processors can attempt to write

into the same location simultaneously but only if they all attempt to write the same value.

Processors

Common Randon Access Memory

120 . . .

1234567

Figure 2.4. A Concurrent Write.

Parallel algorithms are presented in a similar way as in Efficient parallel algorithms by

A. Gibbons and W. Rytter. There is no generally accepted universal language for the

presentation of parallel algorithms. The PRAM is a rather idealized model. We have chosen

this model as a best suitable for the presentation of algorithms and especially for the

presentation of the inherent parallelism of some problems. This would be difficult to nicely

present these algorithms with languages oriented towards concrete existing hardware of parallel

Chapter 2 19 21/7/97

Efficient Algorithms on Texts 19 M. Crochemore & W. Rytter

computer. Moreover, the PRAM model is widely accepted in the literature on parallel

computation on texts.

Parallelism will be expressed by the following type of parallel statement :

for all i in X in parallel do action(i).

Execution of this statement consists of :

— assigning a processor to each element of X;

— executing in parallel by assigned processors the operations specified by action(i).

Usually the part "i in X" looks like "1≤i≤n" if X is an interval of integers. We discuss this more

deeply in Chapter 7.

2.2. Efficiency of algorithms

Efficient algorithms can be classified according to what we mean by efficiency. There are

different notions of efficiency depending on the complexity measure involved. Several such

measures are discussed in this book : sequential time, memory space, parallel time and number

of processors. Our book deals with "feasible" problems. We can define them as problems

having efficient algorithms, or as solvable in time bounded by a small-degree polynomial. In

the case of sequential computations we are interested to lower down the degree of the

polynomial corresponding to time complexity. The most efficient algorithms usually solve a

problem in linear time complexity. We are also interested in space complexity. Optimal space

complexity often means constant number of (small integer) registers in addition to input data.

So, we say that an algorithm is time-space optimal iff it works simultaneously in linear time

and constant extra space. These are the most advanced sequential algorithms, and the most

interesting also both from practical and theoretical point of view.

In the case of parallel computations we are generally interested in the parallel time T(n) as

well as in the number of processors P(n) required for the execution of the parallel algorithm.

The total number of elementary operations performed by the parallel algorithm is not greater

than the product T(n)P(n). Efficient parallel algorithms are those that operate in no more than

polylogarithmic (a polynomial of log’s of input size) time with a polynomial number of

processors. The class of problems solvable by such algorithms is denoted by NC and we call

the related algorithms NC-algorithms. A NC-algorithm is optimal iff the total number of

operations T(n)P(n) is linear. Another possible definition is that this number is essentially the

same as the time complexity of the best known sequential algorithm solving the given problem.

However we adopt here the first option because algorithms on strings usually have a time

complexity at least linear.

Evaluating precisely the complexity of an algorithm according to some measure is often

difficult, and moreover it is unlikely to be of some use. The “big O” notation makes clear what

are the important terms of a complexity expression. It estimates the asymptotic order of the

complexity of an algorithm and helps to compare algorithms between each other. Recall that if f

and g are two function from and to integers, then we say that f = O(g) if f(n)≤C.g(n) when

n>N, for some constants C and N.

We write f = Θ(g) when the functions f and g are of the same order, which means that

both equalities f = O(g) and g = O(f) hold.

Comparing functions through their asymptotic orders leads to these kind of inequalities :

O(n

0.7

) < O(n) < O(n.log(n)), or O(n

log(n)

) < O(log(n)

) < O(n!).

Within sequential models of machine one can distinguish further types of computations :

off-line, on-line and real-time. These types are related also to efficiency. It is understood that

real-time computations are more efficient than general on-line, and that on-line computations

are more efficient than off-line. Each algorithm is an off-line algorithm : "off-line" conceptually

means that the whole input data can be put into the memory before the actual computation

starts. We are not interested then in the intermediate results computed by the algorithm, but

only the final result is sought (though this final result can be a sequence or a vector). The time

complexity is measured by the total time from the moment the computation starts (with all

input data previously memorized) up to the final termination. In contrast, an on-line algorithm

is like a sequential transducer. The portions of the input data are "swallowed" by the algorithm

step after step, and after each step an intermediate result is expected (related to the input data

read so far). It then reads the next portion of the input, and so on. In on-line algorithms the

input can be treated as an infinite stream of data, and so we are not mainly interested in the

termination of the algorithm for all such data. The main interest for us is the total time T(n) for

which we have to wait to get the n-th first outputs. The time T(n) is measured starting at the

beginning of the whole computation (activation of the transducer). Suppose that the input data

is a sequence and that after reading the n-th symbol we want to print "1" if the text read to this

moment contains a given pattern as a suffix, otherwise we print "0". Hence we have two

streams of data : the stream of input symbols and an output stream of answers "1" or "0". The

main feature of the on-line algorithm is that we have to give an output value before reading the

next input symbol.

The real time computations are these on-line algorithms which are in a certain sense optimal;

the elapsing time between reading two consecutive input symbols (the time spent for

computing only the last output value) should be bounded by a constant. Most linear on-line

algorithms are in fact real-time.

We are mostly interested in off-line computations whose worst case time is linear,

however also on-line and real-time computations as well as average complexities will be

sometimes shortly discussed in the book.

Chapter 2 21 21/7/97

Efficient Algorithms on Texts 21 M. Crochemore & W. Rytter

2.3. Notation and formal definitions of basic problems on texts

Let A be an input alphabet — a finite set of symbols. Elements of A are called the letters,

the characters, or the symbols. Typical examples of alphabets are : the set of all ordinary letters,

or the set of binary digits. The texts (also called words or strings) over A are sequences of

elements of A. The length (size) of a text is the number of its elements (with repetitions). So,

the length of aba is 3. The length of a word x is denoted by |x|. The input data for our problems

will be words and the size n of the input problem will be usually the length of the input word.

In some situations, n will denote the maximum length or the total length of several words if the

input of the problem consists of several words.

The i-th element of the word x is denoted by x[i] and i is its position in x. We denote by x[i…j]

the subword x[i]x[i+1]…x[j] of x. If i>j, by convention, the word x[i…j] is the empty word (the

sequence of length zero).

We say that the word x of length n is a factor (also called a subword) of the word y if

x=y[i+1…i+n] for some integer i. We also say that x occurs in y at position i or that the

position i is a match for x in y.

We define also the notion of a subsequence (sometimes called a subword). The word x is

a subsequence of y if x can be obtained from y by removing zero or more (non necessarily

adjacent) letters from it. Equivalently x is a subsequence of y if x=y[i

]y[i

]…y[i

], where i

, …, i

is an increasing sequence of indices in y.

Below we define basic problems and groups of problems covered in the book. We often

consider two texts pat (the pattern) and text of respective lengths m and n.

1. String-matching (the basic problem)

Given texts pat and text, verify if pat occurs in text. Hence it is a decision problem : the

output is a boolean value. It is usually assumed that m≤n. So, the size of the problem is n.

A slightly advanced version is to search for all occurrences of pat in text, that is, to compute the

set of positions of pat in text.. Denote by MATCH(pat, text) this set. In most cases an algorithm

computing MATCH(pat, text) is a trivial modification of the decision algorithm, hence we

sometimes present only the decision algorithm for string-matching.

Instead of one pattern one can consider a finite set of patterns and ask if a given text text

contains a pattern from this set. The size of the problem is now the total length of all patterns

plus the length of text.

2. Construction of string-matching automata

For a given pattern pat, construct the minimal deterministic finite automaton accepting all

words containing pat as a suffix. Denote such an automaton by SMA(pat). A more general

problem is to construct a similar automaton SMA(∏) accepting the set of all words containing

as a suffix one of the patterns from the set ∏={pat

, …, pat

}

3. Approximate string-matching

We are given again a pattern pat and a text text. The problem consists in finding an

approximate occurrence of pat in text, that is, a position i such that dist(pat, text[i+1…i+m]) is

minimal. Another instance of the problem is to find all positions i such that dist(pat,

text[i+1…i+m]) is less than a given constant. Here, dist is a function defining a distance

between two words. There are two standard distances : the Hamming distance (number of

positions at which two strings differ) and the edit distance (see Problem 7 below).

4. String-matching with don't care symbols

We are given a special universal symbol

ø that matches any other symbol (including

itself). It is called the “don't care symbol”. In fact, ø can be a common name for several

unimportant symbols of the alphabet. For two symbols a and b, we write a≈b iff they are equal

or at least one of them is a don't care symbol. For two words of the same length we write x≈y

if, for each i, x[i]≈y[i].

The problem consists in verifying whether pat≈text[i+1…i+m] for some i, or more

generally, to compute the set of all such positions i.

5. Two-dimensional pattern matching

For this problem, the pattern pat and the text text are two-dimensional arrays (or

matrices) whose elements are symbols. We are to answer whether pat occurs in text as a

subarray, or to find all positions of pat in text . The approximate and don't care versions of the

problem can be defined similarly as for the (one-dimensional) string-matching problem.

Instead of arrays one can also consider some other "shapes", e.g. trees.

6. Longest common factor

Compute the maximal length of longest common factors of two words x, y (denoted by

LCF(x, y)). One can consider also longest common factors for more than two words.

7. Edit distance

Compute the edit distance, EDIT(

x, y), between two words. It is the minimal number of

edit operations needed to transform one string into the other. Edit operations are : insertion of

one character, deletion of one character, and change of one character.

The problem is closely related to the approximate string-matching and to the problem defined

below. It is similar to the notion of alignment of DNA sequences in Molecular Biology.

8. Longest common subsequence

剩余395页未读，继续阅读

weixin_38743968

粉丝: 404
资源: 2万+

文本算法实战：理论与应用深度解析

算法 Algorithms 1.1 答案

近似算法 Approximation Algorithms 中文课件.ppt

算法 algorithms(中文第4版)

分别解释下Continuous control algorithms和Discrete control algorithms

list of synthesis algorithms什么意思

线上算法和离线算法区别

introduction to algorithms 3rd

aes加密算法实现python

python中hashlib模块中algorithms_guaranteed()的作用？所需参数？简单案例？

最新资源