A Statistical Model for Flexible String Similarity

1 Introduction

String matching is an important problem. Many studies have been done on this problem and developed methods are ap­ plied to various problems such as approximate information retrieval from OCR processed and spoken documents, pattern extraction from sensor data and so on.

In order to measure the similarity of strings, edit distance and DP matching have been frequently used. In the edit dis­ tance, similarity is defined as the minimum number of oper­ ations of insertion, deletion and replacement required to con­ vert one string to another. The DP matching allows us to use weights of the operations which enable flexible definition of string similarity according to objective problems. However, weights should be determined depending on the problem and it is hard work to find appropriate weights manually.

This problem motivates us to develop a statistical model which has high expressive power of string similarity and whose parameters can be learned from training data. This pa­ per proposes a statical model called dual and variable length hidden Markov model (DVHMM) and applies it to structured string analysis.

2 Statistical Model for String Similarity

For a base string and a compared string, DVHMM defines their similarity by decomposing them into pairs of substrings and combining the similarities of the substrings.

A DVHMM is a form of Hidden Markov Model (HMM). Instead of producing a string, state transitions of DVHMM produce a pair of strings. Each state of the DVHMM defines the similarity of pairs of strings of fixed lengths in the form of output probability. A state is characterized by a pair of lengths. For example, a state characterized by a pair (2, I) of lengths defines similarities of two consecutive characters in a base string and one character in a compared string. A state ~1,0) means t~at the length of the base (resp. compared) string 1s 1 (resp. 0), 1.e., a delete operation, whereas a state (0, 1) cor­ responds to an insert operation. A state ( 1,1) corresponds to both a replacement operation and equivalent mapping. Gen­ erally, the state corresponding to a pair ( i, j) produces a pair ?f strings whose base string (resp. compared string) length ~s i (resp. j) with certain probability. States are categorized mto non-null state that produces a pair of base and compared strings, and null state that produces null output and controls state transitions.

Figure 1 shows an example of DVHMM that consists of five non-null states which define the similarity of pairs of substrings of length (1 ,0),(0, 1 ),(1, 1 ),(2, 1) and (1 ,2). In this figure, output symbols are omitted due to space restrictions. Suppose the alphabet is { a,b}. Then, the output symbols of the state (2, 1) are

{ (aa,a),(aa,b),(ab,a),(ab,b),(ba,a), (ba,b),(bb,a),(bb,b)} and output probability is asigned to each output symbol.

DVHMM defines joint probability distribution of a pair of strings. Let us consider a base string "ab" and a compared string "a". Then, the DVHMM in Figure 1 produces the pair of strings (ab, a) by one of the following six sequences of state transitions.

N1RwN1RwNtRoi NIR1oNil1~1N1Rto NIRoiNIRlONtRw N1RwNtR11 N1RnN1R10 NIR21

Then, the joint probability of (ab,a) is obtained by summing the probabilities of all the five sequences of transitions. For­ mally, for a base string b and a compared string c, the joint probability of them is obtained by

where Q is a set of state transitions producing (b, c) and P(b, c, q) is the joint probability of (b, c) along the state tran­ sition q. The joint probability is used as the similarity of a pair of strings.

DVHMM inherits HMM's ability to represent syntactical structure. This ability enables DVHMM to change similar­ ity definition depending on the part of strings. Let us con­ sider strings consisting of two components delimited by spe­ cial characters. For example, base string consists of two parts delimited by colon and compared string is concatenation of two parts without delimiters. Then, the DVHMM depicted in Figure 2 defines the similarity of these strings, i.e., a com­ ponent DVHMM C1 defines similarity of prefix component whereas a component DVHMM C2 defines the similarity of suffix component. State N3 defines the delimiter, which pro­ duce a pair of colon and null string with probability 1.0. For a given pair ("a:ab", "ab") of string, the DVHMM may separate the pair into ("a","a") as a prefix component and ("b","b") as a suffix component, and similarities of these components are measured by different similarity measures, i.e., C1 and C2 , respectively. In this case, similarity can be calculated by the joint probability of the pair of string produced by the most likely state transition, i.e. ,

where Q is the same set in expression (1).

Probabilities of DVHMM can be estimated from train­ ing data by the expectation-maximization technique efficiently[Takasu, 2002]. For a given pair (b, c) of strings, the similarity (2) can be calculated efficiently by a dy­ namic programming algorithm. We omit the details of the algorithms due to space restriction.

Compared with DP matching, DVHMM enables to

• define the weights in a more detailed manner, and
• calculate the weights systematically.

3 Preliminary Experiment

We applied the proposed method to bibliographic matching which matches references in academic articles with records in bibliographic databases. Reference information is effec­ tively used in digital libraries such as CiteSeer [Lawrence, 1999]. In bibliographic references, bibliographic components such as author's name and article title are located in a specific order and separated by delimiters. The syntactical structure of bibliographic reference can be represented with graphical structure of finite automaton where each state represents a bibliographic component. A DVHMM for bibliographic ref­ erences is obtained by replacing each state with a component DVHMM like Figure 2 where each component DVHMM de­ fines the similarity of the corresponding bibliographic com­ ponent. For example, because journal names are often ab­ breviated, higher probabilities are assigned to deletion er­ rors in the DVHMM for journal name whereas low proba­ bilities are assigned to the deletion errors for page because it is seldom abbreviated in references. In this way, the simi­ larity is changed depending on the bibliographic components, and consequently, more accurate similarity model can be con­ structed for structured strings.

We carried out an experiment on approximate string match­ ing. In this experiment, we prepared 1,575 references appeared in Japanese academic articles and corresponding records in a bibliographic database, then applied 5-fold cross­ validation, i.e., divided them into 5 groups, trained DVHMM using 4 groups of them, and made bibliographic matching us­ ing remaining one group. Matching result is ranked records in the database according to the similarity. We used edit dis­ tance as baseline similarity and compared the performance of the proposed method with the edit distance. The following table shows the average accuracy that the correct record is ranked within top m records.

As shown in the table the proposed method achieved higher matching accuracy.

4 Conclusion

This paper proposed a statistical model for defining string similarity. The proposed model can represent similarity of strings with the similarities of substrings such as traditional edit distance and DP matching. However, the proposed model can define the similarity more flexible way. This paper shows the proposed model can be applied to the matching of struc­ tured strings.