In phonetic search, the goal is to nd in a text all words with the same pronunciation as the search phrase. The user writes the word down using a di erent alphabet and transcription rules. Mrazova et al. proposed a new method for phonetic search based on searching for all possible transcriptions with Aho-Corasick automata [8]. Their algorithm o ers better precision than the previous existing algorithms for phonetic search, but the size of the search automata grows exponentially with the length of the search phrase. In this paper, we examine the utilisation of the states of the automata created by this approach, and we discuss a memory-e cient implementation of the automata exploiting the fact that many states of the automaton are never visited during the search phase. We demonstrate that this implementation is comparable in search speed to the original automata, but it leads to signi cant memory savings.
In the current world, the amount of information grows at an ever increasing rate and searching for information is one of the most common tasks. Specifying the right query is a di cult task by itself and it is even more complicated when the data is in a foreign language with di erent transcription rules or alphabet. Phonetic search is an approach to string matching that nds not just the exact search phrase, but it also nds all phrases that are pronounced in a similar way in the language of the text.
Mrazova et al. [
The rst phonetic search algorithm Soundex was published by Russel [
The Soundex-based algorithms typically have very high recall, but low
precision. Mrazova et al. [
Aho-Corasick automata provide strong guarantees on the worst-case time
complexity, but the practical e ciency depends signi cantly on e ective
utilization of CPU caches and memory transfers [
Complexity of Phonetic Search
The main idea of the approach of Mrazova et al. [
Because the transcription rules are context-free, any combination of them can be applied to the search phrase, provided they cover the whole search phrase and do not overlap. As a result, the number of possible possible transcriptions grows exponentially with the length of the search phrase. Table 1 shows the number of possible transcriptions and states of the Aho-Corasick automaton matching all these transcriptions for selected Arabic and German words.
While the number of possible transcriptions grows rapidly with the length of the search phrase, most of these transcriptions do not exist as words in the language of the text. To demonstrate this, we have constructed the automata for selected Arabic and German words and measured how many times each state was visited when processing a 250 MB sample of text extracted from the Arabic and German Wikipedia. The results are summarized in Table 2.
The experiment con rmed that most of the states are never visited. In particular, the automaton spends 99 % of time in ca 10 states. These numbers are even more striking if you compare them with the numbers of states shown in Table 1. The automaton construction would be signi cantly more e ective if it could avoid building the states and transitions that are never used. This can be achieved multiple ways: 1. A dictionary can be used to restrict the generated transcriptions to existing words. This is an e ective approach, but it reduces the recall of the algorithm and it can be used only for common words. Many words such as names of places and people do not appear in any dictionary. In Arabic text, foreign names can be written down using multiple di erent transcriptions. 2. The dictionary can be created from the searched text. Creating such a dictionary requires a considerable amount of computing resources and it is not possible if the text is not known in advance, e. g. in network monitoring. 3. Alternatively, one may use the transcription rules to create a non-deterministic nite automaton (NFA) from the search phrase. The automaton is rst created as a chain of states accepting exactly the search phrase. Then, edges and sequences of states are added according to the transcription rules. An example of such NFA is shown on Fig. 1. The NFA is very compact, but the time complexity of the search is O(nl), where l is the number of states of the NFA and n is the length of the text. Compared to the AC-A, the NFAs are remarkably slower even for short search phrases.
0
1 r er aa, ah a
2
ei, ai, ay, ey
i, y
j
3
s
z
4
ä, äh, ee,
eh, ö, öh
e
5
Lazy Construction of Aho-Corasick Automata
We have shown that in phonetic search, the number of states visited at least once
during the search is very low compared to the total number of states. Instead
of determining which words appear in the text, our implementation adds states
to the automaton lazily when they are required by the text, similar to the lazy
evaluation of transitions described by Aho et al. [2, Ch. 3.7]. This is achieved
by merging the construction and search phases of the original Aho-Corasick
algorithm into a single loop driven by the searched text. In conformity with [
During the initialization, a minimal automaton containing only the initial state and its direct descendants is created. The automaton reads one character from the text at a time, and changes the current state using the goto or failure functions g and f in the same way as the original Aho-Corasick algorithm. When a state s is visited for the rst time, it is expanded, i. e. its direct descendant states are added to the automaton, and the functions f , g, and out are updated accordingly. If the state f (s) was not expanded yet, it is expanded before out(s) is updated. Instead of presenting the pseudo-code of the algorithm, we illustrate its operation on Fig. 2. The gure shows how states are created and expanded when searching for the words he, she and hers in the text usher.
To be able to expand states when needed, it is necessary to keep more information about the states than in the original algorithm. Each state s needs to 0 he hers she s h 0 he hers she 1 she 2 he hers (3) h e 0 he hers she (1) s h 1 she 2 he hers 3 she 5 he hers s h e
4 she, he 1 she 2 he hers h e 0 he hers she (5) 3 she 5 he hers 0 he hers she e r s h s h (2) 1 she 2 he hers 1 she 2 he hers h (4) h e 3 she 3 she 5 he hers 4 she, he 6 hers s 7 hers e r
4 she, he 6 hers store the set of search phrases accepted by the descendants of s. This set can be represented as a set of states of the NFA for the search phrase as described in Sect. 1. In case of phonetic search, the number of states of the NFA is linear in the size of the search phrase, which makes this representation particularly e ective.
The correctness of the modi ed algorithm can be proved the same way as for the original Aho-Corasick algorithm. Moreover, it can also be proved that the modi ed algorithm has the same asymptotic time complexity.
To show the e ciency of the Lazy AC-A and compare it with searching with the
original AC-A, we have implemented the algorithm as a C++ program. All tests
were run on a laptop with 2.4 GHz Intel Core 2 Duo CPU and 2 GB of RAM,
running a 32-bit version of Ubuntu Linux, with code compiled using GCC 4.3.
The text used in the experiments was a selection of pages from static dumps
of Arabic and German Wikipedia [
We have implemented the version of the algorithm that uses NFAs as a compact representation of the set of search phrases. To further improve the speed of processing of the text, whenever the algorithm uses the function f to do a state transition, it adds this transition to the function g. For the implementation of the original AC-A, we have chosen the faster deterministic version, where all transitions are stored directly in the function g.
The rst set of experiments was aimed at the raw speed of string matching. We have used the algorithm with various German and Arabic words, with transcription lengths ranging from four to fourteen characters. We have measured the time necessary to process a single character of the text. In case of the original AC-A, we did not take into account the time necessary to build the automaton. It shows that both for the Lazy AC-A and the original AC-A, the times to perform a single state transition are almost the same, independent on the length of the transcription, and they are almost independent on the language used. The results are summarized in Table 3. It shows, that for both languages, the unmodi ed AC-A's are approximately 19 % faster than the Lazy AC-A.
The amount of memory necessary to represent a single state only depends on the alphabet of the text, but not on the search phrase or the searched text. To assess the memory requirements of the modi ed algorithm, we have measured the number of expanded and unexpanded states, and compared it to the number of states of the corresponding AC-A. The results are summarized in Table 4. While the number of states of the original AC-A grows exponentially with the length of the phonetic transcription, the size of the NFA grows linearly, and it remains reasonably small even for larger phrases, and also the growth of the number of expanded and unexpanded states of the Lazy AC-A is relatively slow and for German words it even stops at ca 60 states. We assume, that a similar but higher upper bound also exists for the Arabic words.
The modi ed algorithm retains the asymptotic complexity of the original ACA. On the other hand, while the original AC-A can guarantee that every state transition will be done in a constant time, the modi ed version of the algorithm does not have this property. The expansion of the failure function f in state s may lead to expanding all states between the current state and the initial state. This may have important consequences in applications like network monitoring, where an attacker can send packets with keywords that would require expanding new states in each step.
While the number of states created by the modi ed algorithm is usually far lower than m, it is possible to create such set of search phrases and text, that all m states will be created. Except for special cases (e. g. when there is just a single search phrase), the memory requirements can be kept low by disposing states that are not required at the moment, and re-creating them when they are needed again. When the automaton is in state s, then all states s0 : depth(s0) > depth(s) can be removed safely. Specially, when the automaton is in the initial state, all states except the initial one can be removed. Naturally, this would have a negative impact on the running time.
In this paper, we have shown a memory-e ective implementation of the AhoCorasick algorithm. In the worst case the modi ed algorithm has asymptotically the same time complexity as the original AC-A, but it only creates states that are visited by the automaton when processing a given text. This brings a great advantage in applications like phonetic search, where the set of search phrases is extremely large, but it can be represented as a relatively small non-deterministic automaton, and most of the search phrases never appear in a real text. We have shown experimentally that in phonetic search the speed of the modi ed algorithm is comparable to the original AC-A even if the construction of the AC-A is not taken into account, and in practice it successfully avoids the exponential growth of the number of states.