1Approx(3) User Contributed Perl Documentation Approx(3)
2
6 String::Approx - Perl extension for approximate matching (fuzzy
7 matching)
8
10 use String::Approx 'amatch';
11 print if amatch("foobar");
13 my @matches = amatch("xyzzy", @inputs);
15 my @catches = amatch("plugh", ['2'], @inputs);
17
19 String::Approx lets you match and substitute strings approximately.
20 With this you can emulate errors: typing errorrs, speling errors,
21 closely related vocabularies (colour color), genetic mutations (GAG
22 ACT), abbreviations (McScot, MacScot).
23 NOTE: String::Approx suits the task of string matching, not string
25 comparison, and it works for strings, not for text.
26 If you want to compare strings for similarity, you probably just want
28 the Levenshtein edit distance (explained below), the Text::Levenshtein
29 and Text::LevenshteinXS modules in CPAN. See also Text::WagnerFischer
30 and Text::PhraseDistance. (There are functions for this in
31 String::Approx, e.g. adist(), but their results sometimes differ from
32 the bare Levenshtein et al.)
33 If you want to compare things like text or source code, consisting of
35 words or tokens and phrases and sentences, or expressions and
36 statements, you should probably use some other tool than
37 String::Approx, like for example the standard UNIX diff(1) tool, or the
38 Algorithm::Diff module from CPAN.
39 The measure of approximateness is the Levenshtein edit distance. It is
41 the total number of "edits": insertions,
42 word world
44 deletions,
46 monkey money
48 and substitutions
50 sun fun
52 required to transform a string to another string. For example, to
54 transform "lead" into "gold", you need three edits:
55 lead gead goad gold
57 The edit distance of "lead" and "gold" is therefore three, or 75%.
59 String::Approx uses the Levenshtein edit distance (tLed) as its
61 measure, but String::Approx is not well-suited for comparing the tLeds
62 of strings, in other words, if you want a "fuzzy eq", see above.
63 Strings::Approx is more like regular expressions or index(), it finds
64 substrings that are close matches.
65
67 use String::Approx 'amatch';
68 $matched = amatch("pattern")
70 $matched = amatch("pattern", [ modifiers ])
71 $any_matched = amatch("pattern", @inputs)
73 $any_matched = amatch("pattern", [ modifiers ], @inputs)
74 @match = amatch("pattern")
76 @match = amatch("pattern", [ modifiers ])
77 @matches = amatch("pattern", @inputs)
79 @matches = amatch("pattern", [ modifiers ], @inputs)
80 Match pattern approximately. In list context return the matched
82 @inputs. If no inputs are given, match against the $_. In scalar
83 context return true if any of the inputs match, false if none match.
84 Notice that the pattern is a string. Not a regular expression. None
86 of the regular expression notations (^, ., *, and so on) work. They
87 are characters just like the others. Note-on-note: some limited form
88 of "regular expressionism" is planned in future: for example character
89 classes ([abc]) and any-chars (.). But that feature will be turned on
90 by a special modifier (just a guess: "r"), so there should be no
91 backward compatibility problem.
92 Notice also that matching is not symmetric. The inputs are matched
94 against the pattern, not the other way round. In other words: the
95 pattern can be a substring, a submatch, of an input element. An input
96 element is always a superstring of the pattern.
97 MODIFIERS
99 With the modifiers you can control the amount of approximateness and
100 certain other control variables. The modifiers are one or more
101 strings, for example "i", within a string optionally separated by
102 whitespace. The modifiers are inside an anonymous array: the [ ] in
103 the syntax are not notational, they really do mean [ ], for example [
104 "i", "2" ]. ["2 i"] would be identical.
105 The implicit default approximateness is 10%, rounded up. In other
107 words: every tenth character in the pattern may be an error, an edit.
108 You can explicitly set the maximum approximateness by supplying a
109 modifier like
110 number
112 number%
113 Examples: "3", "15%".
115 Note that "0%" is not rounded up, it is equal to 0.
117 Using a similar syntax you can separately control the maximum number of
119 insertions, deletions, and substitutions by prefixing the numbers with
120 I, D, or S, like this:
121 Inumber
123 Inumber%
124 Dnumber
125 Dnumber%
126 Snumber
127 Snumber%
128 Examples: "I2", "D20%", "S0".
130 You can ignore case ("A" becames equal to "a" and vice versa) by adding
132 the "i" modifier.
133 For example
135 [ "i 25%", "S0" ]
137 means ignore case, allow every fourth character to be "an edit", but
139 allow no substitutions. (See NOTES about disallowing substitutions or
140 insertions.)
141 NOTE: setting "I0 D0 S0" is not equivalent to using index(). If you
143 want to use index(), use index().
144
146 use String::Approx 'asubstitute';
147 @substituted = asubstitute("pattern", "replacement")
149 @substituted = asubstitute("pattern", "replacement", @inputs)
150 @substituted = asubstitute("pattern", "replacement", [ modifiers ])
151 @substituted = asubstitute("pattern", "replacement",
152 [ modifiers ], @inputs)
153 Substitute approximate pattern with replacement and return as a list
155 <copies> of @inputs, the substitutions having been made on the elements
156 that did match the pattern. If no inputs are given, substitute in the
157 $_. The replacement can contain magic strings $&, $`, $' that stand
158 for the matched string, the string before it, and the string after it,
159 respectively. All the other arguments are as in "amatch()", plus one
160 additional modifier, "g" which means substitute globally (all the
161 matches in an element and not just the first one, as is the default).
162 See "BAD NEWS" about the unfortunate stinginess of "asubstitute()".
164
166 use String::Approx 'aindex';
167 $index = aindex("pattern")
169 @indices = aindex("pattern", @inputs)
170 $index = aindex("pattern", [ modifiers ])
171 @indices = aindex("pattern", [ modifiers ], @inputs)
172 Like "amatch()" but returns the index/indices at which the pattern
174 matches approximately. In list context and if @inputs are used,
175 returns a list of indices, one index for each input element. If
176 there's no approximate match, "-1" is returned as the index.
177 NOTE: if there is character repetition (e.g. "aa") either in the
179 pattern or in the text, the returned index might start "too early".
180 This is consistent with the goal of the module of matching "as early as
181 possible", just like regular expressions (that there might be a "less
182 approximate" match starting later is of somewhat irrelevant).
183 There's also backwards-scanning "arindex()".
185
187 use String::Approx 'aslice';
188 ($index, $size) = aslice("pattern")
190 ([$i0, $s0], ...) = aslice("pattern", @inputs)
191 ($index, $size) = aslice("pattern", [ modifiers ])
192 ([$i0, $s0], ...) = aslice("pattern", [ modifiers ], @inputs)
193 Like "aindex()" but returns also the size (length) of the match. If
195 the match fails, returns an empty list (when matching against $_) or an
196 empty anonymous list corresponding to the particular input.
197 NOTE: size of the match will very probably be something you did not
199 expect (such as longer than the pattern, or a negative number). This
200 may or may not be fixed in future releases. Also the beginning of the
201 match may vary from the expected as with aindex(), see above.
202 If the modifier
204 "minimal_distance"
206 is used, the minimal possible edit distance is returned as the third
208 element:
209 ($index, $size, $distance) = aslice("pattern", [ modifiers ])
211 ([$i0, $s0, $d0], ...) = aslice("pattern", [ modifiers ], @inputs)
212
214 use String::Approx 'adist';
215 $dist = adist("pattern", $input);
217 @dist = adist("pattern", @input);
218 Return the edit distance or distances between the pattern and the input
220 or inputs. Zero edit distance means exact match. (Remember that the
221 match can 'float' in the inputs, the match is a substring match.) If
222 the pattern is longer than the input or inputs, the returned distance
223 or distances is or are negative.
224 use String::Approx 'adistr';
226 $dist = adistr("pattern", $input);
228 @dist = adistr("pattern", @inputs);
229 Return the relative edit distance or distances between the pattern and
231 the input or inputs. Zero relative edit distance means exact match,
232 one means completely different. (Remember that the match can 'float'
233 in the inputs, the match is a substring match.) If the pattern is
234 longer than the input or inputs, the returned distance or distances is
235 or are negative.
236 You can use adist() or adistr() to sort the inputs according to their
238 approximateness:
239 my %d;
241 @d{@inputs} = map { abs } adistr("pattern", @inputs);
242 my @d = sort { $d{$a} <=> $d{$b} } @inputs;
243 Now @d contains the inputs, the most like "pattern" first.
245
247 "String::Approx" maintains a LU (least-used) cache that holds the
248 'matching engines' for each instance of a pattern+modifiers. The cache
249 is intended to help the case where you match a small set of patterns
250 against a large set of string. However, the more engines you cache the
251 more you eat memory. If you have a lot of different patterns or if you
252 have a lot of memory to burn, you may want to control the cache
253 yourself. For example, allowing a larger cache consumes more memory
254 but probably runs a little bit faster since the cache fills (and needs
255 flushing) less often.
256 The cache has two parameters: max and purge. The first one is the
258 maximum size of the cache and the second one is the cache flushing
259 ratio: when the number of cache entries exceeds max, max times purge
260 cache entries are flushed. The default values are 1000 and 0.75,
261 respectively, which means that when the 1001st entry would be cached,
262 750 least used entries will be removed from the cache. To access the
263 parameters you can use the calls
264 $now_max = String::Approx::cache_max();
266 String::Approx::cache_max($new_max);
267 $now_purge = String::Approx::cache_purge();
269 String::Approx::cache_purge($new_purge);
270 $limit = String::Approx::cache_n_purge();
272 To be honest, there are actually two caches: the first one is used far
274 the patterns with no modifiers, the second one for the patterns with
275 pattern modifiers. Using the standard parameters you will therefore
276 actually cache up to 2000 entries. The above calls control both caches
277 for the same price.
278 To disable caching completely use
280 String::Approx::cache_disable();
282 Note that this doesn't flush any possibly existing cache entries, to do
284 that use
285 String::Approx::cache_flush_all();
287
289 Because matching is by substrings, not by whole strings, insertions and
290 substitutions produce often very similar results: "abcde" matches
291 "axbcde" either by insertion or substitution of "x".
292 The maximum edit distance is also the maximum number of edits. That
294 is, the "I2" in
295 amatch("abcd", ["I2"])
297 is useless because the maximum edit distance is (implicitly) 1. You
299 may have meant to say
300 amatch("abcd", ["2D1S1"])
302 or something like that.
304 If you want to simulate transposes
306 feet fete
308 you need to allow at least edit distance of two because in terms of our
310 edit primitives a transpose is first one deletion and then one
311 insertion.
312 TEXT POSITION
314 The starting and ending positions of matching, substituting, indexing,
315 or slicing can be changed from the beginning and end of the input(s) to
316 some other positions by using either or both of the modifiers
317 "initial_position=24"
319 "final_position=42"
320 or the both the modifiers
322 "initial_position=24"
324 "position_range=10"
325 By setting the "position_range" to be zero you can limit (anchor) the
327 operation to happen only once (if a match is possible) at the position.
328
330 Major release 3.
331
333 GOOD NEWS
334 The version 3 is 2-3 times faster than version 2
335 No pattern length limitation
336 The algorithm is independent on the pattern length: its time
337 complexity is O(kn), where k is the number of edits and n the
338 length of the text (input). The preprocessing of the pattern will
339 of course take some O(m) (m being the pattern length) time, but
340 "amatch()" and "asubstitute()" cache the result of this
341 preprocessing so that it is done only once per pattern.
342 BAD NEWS
344 You do need a C compiler to install the module
345 Perl's regular expressions are no more used; instead a faster and
346 more scalable algorithm written in C is used.
347 "asubstitute()" is now always stingy
349 The string matched and substituted is now always stingy, as short
350 as possible. It used to be as long as possible. This is an
351 unfortunate change stemming from switching the matching algorithm.
352 Example: with edit distance of two and substituting for "word" from
353 "cork" and "wool" previously did match "cork" and "wool". Now it
354 does match "or" and "wo". As little as possible, or, in other
355 words, with as much approximateness, as many edits, as possible.
356 Because there is no need to match the "c" of "cork", it is not
357 matched.
358 no more "aregex()" because regular expressions are no more used
360 no more "compat1" for String::Approx version 1 compatibility
361
363 The following people have provided valuable test cases, documentation
364 clarifications, and other feedback:
365 Jared August, Arthur Bergman, Anirvan Chatterjee, Steve A. Chervitz,
367 Aldo Calpini, David Curiel, Teun van den Dool, Alberto Fontaneda, Rob
368 Fugina, Dmitrij Frishman, Lars Gregersen, Kevin Greiner, B. Elijah
369 Griffin, Mike Hanafey, Mitch Helle, Ricky Houghton, 'idallen', Helmut
370 Jarausch, Damian Keefe, Ben Kennedy, Craig Kelley, Franz Kirsch, Dag
371 Kristian, Mark Land, J. D. Laub, John P. Linderman, Tim Maher, Juha
372 Muilu, Sergey Novoselov, Andy Oram, Ji Y Park, Eric Promislow, Nikolaus
373 Rath, Stefan Ram, Slaven Rezic, Dag Kristian Rognlien, Stewart Russell,
374 Slaven Rezic, Chris Rosin, Pasha Sadri, Ilya Sandler, Bob J.A.
375 Schijvenaars, Ross Smith, Frank Tobin, Greg Ward, Rich Williams, Rick
376 Wise.
377 The matching algorithm was developed by Udi Manber, Sun Wu, and Burra
379 Gopal in the Department of Computer Science, University of Arizona.
380
382 Jarkko Hietaniemi <jhi@iki.fi>
383
385 Copyright 2001-2005 by Jarkko Hietaniemi
386 This library is free software; you can redistribute it and/or modify it
388 under the same terms as Perl itself.
389 Furthermore: no warranties or obligations of any kind are given, and
391 the separate file COPYRIGHT must be included intact in all copies and
392 derived materials.
393perl v5.12.0 2006-04-09 Approx(3)