Showing posts with label data-structure. Show all posts
Showing posts with label data-structure. Show all posts

Thursday, February 06, 2014

Substring matching using Aho-Corasick and Redis


The Aho-Corasick algorithm is a fast string matching algorithm that can match a large set of keywords simultaneously against incoming text. It does this by using a trie like data structure, and attempting to navigate the tree along nodes corresponding to characters in the keywords.

The first phase builds up the trie by reading through each keyword in the dictionary, and building nodes for each character in each keyword if it doesn't already exist. To each node, it attaches a set of "transition" nodes - ie, characters it can traverse to from the current character given the set of keywords. Additionally, the keyword itself is associated with the character that ends it. The tree building complexity is linear, O(m) where m is the number of characters across all keywords.

Once the keyword trie is built, searching it is accomplished in a single pass through the text to be matched. The search process recovers substrings which occur in the keywords from the dictionary. The complexity of search is also linear, O(n) where n is the size of the input text, since all keywords are matched simultaneously.

Even though the build time is linear, it can become significant for large dictionaries. If the dictionary is relatively static, the trie building step can be avoided by storing it in a non-volatile key-value store such as Redis. Since Redis operates on in-memory data, you get the best of both worlds - no startup penalty and search speeds almost as good as using in-memory data structures.

In this post, I describe a small (and incomplete, but sufficient for my purposes) implementation of the Aho-Corasick algorithm in Scala that relies on Redis to store the keyword trie. It is similar to the (also slightly modified) Python implementation described in this Sidelines blog post.

Here is the code for the algorithm. The prepare() method takes in a list of keywords and builds a Redis-backed data structure that of two Maps of Sets keyed by the current character, the first one representing the transitions and the second the results (keywords). The search() method takes a phrase to be searched and returns the List of substrings which matches words in the keyword list.

1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// Source: src/main/scala/com/mycompany/solr4extras/dictann/AhoCorasickRedis.scala
package com.mycompany.solr4extras.dictann

import com.redis.RedisClient
import scala.collection.mutable.ArrayBuffer

class AhoCorasickRedis {

  val redis = new RedisClient("localhost", 6379)
  
  def prepare(keywords: List[String]): Unit = {
    keywords.foreach(keyword => {
      var prevCh = '\0'
      keyword.foreach(ch => {
        redis.sadd(tkey(prevCh), ch)
        prevCh = ch
      })
      redis.sadd(rkey(prevCh), keyword)
    })
  }
  
  def search(phrase: String): List[String] = {
    val matches = ArrayBuffer[String]()
    var prevCh = '\0'
    phrase.foreach(ch => {
      prevCh = if (redis.sismember(tkey(prevCh), ch)) ch 
               else '\0'
      val cmatches = redis.smembers(rkey(prevCh)) match {
        case Some(results) => results.flatten
        case None => List() 
      }
      matches ++= cmatches
    })
    matches.toSet.toList
  }
  
  def tkey(ch: Char) = "trn:" + ch
  def rkey(ch: Char) = "res:" + ch
}

To test this, we run the following simple JUnit test which loads the trie with three strings and then searches it using a sentence containing these 3 strings. As you can see, the algorithm finds the 3 strings we expect it to find.

1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
// Source: src/test/scala/com/mycompany/solr4extras/dictann/AhoCorasickRedisTest.scala
package com.mycompany.solr4extras.dictann

import org.junit.Test
import org.junit.Assert

class AhoCorasickRedisTest {

  @Test
  def testBuild(): Unit = {
    val aho = new AhoCorasickRedis()
    aho.prepare(List("Seahawks", "Broncos", "Super Bowl"))
    val matches = aho.search(
      "The Seahawks defeated the Broncos at the Super Bowl.")
    Console.println("matches=" + matches)
    Assert.assertEquals(3, matches.size)
    Assert.assertTrue(matches.contains("Seahawks"))
    Assert.assertTrue(matches.contains("Broncos"))
    Assert.assertTrue(matches.contains("Super Bowl"))
  }
}

For more information about this algorithm, Pekka Kilpelainen's lecture slides provides lots of detail, and Ivan Kuckir's Blog post has a nice animation that illustrates how it works. Both links are also listed under the External Links section in the algorithm's Wikipedia page (referenced earlier).


Posted by Sujit Pal at 6:51 PM 4 comments

Labels: , , ,

Share/Save: Digg Technorati Delicious StumbleUpon Reddit BlinkList Furl Mixx Facebook Google Bookmark Yahoo

Saturday, September 17, 2011

Using an Adjacency Map to match Multi-word Phrases

I recently run our entire taxonomy of approximately 1 million medical concepts through my UIMA Aggregate AE for taxonomy mapping described here, and it took 3 weeks. That's right, 3 weeks.

After I was done questioning my programming skills (or lack of it), I began wondering where all the time was being spent. Almost off the bat, I discovered that I had made the newbie mistake of not reusing cursors when reading from the database (its been a while since I've written straight JDBC code), resulting in the code opening and closing each cursor (some up to 20 times) for each of the 1M concepts. Still, that alone could not explain the long run time, so the next candidate was the UIMA AE itself.

Back in my CNET days, over one very late night, I learned to profile applications by inserting stopwatch calls into (my slow) code, and the lesson has stuck (thanks Adam :-)). I wanted to do the same thing here, ie, for a aggregate AE (consisting of a fixed flow of primitive AEs), I wanted to find the time taken within each primitive AE - then I could identify the AEs that needed improvement.

Since the primitive AE is controlled by the UIMA framework, the only way to get a handle to a StopWatch (the only way I know of, anyway) from within each primitive AE is to expose the StopWatch statically via a Singleton holder class, something like this:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// Source: src/main/java/com/mycompany/tgni/uima/utils/StopwatchHolder.java
package com.mycompany.tgni.uima.utils;

import org.springframework.util.StopWatch;

public class StopwatchHolder {

  private static StopwatchHolder holder = new StopwatchHolder();
  private static StopWatch instance;
  
  private StopwatchHolder() {
    instance = new StopWatch();
  }
  
  public static StopWatch instance() {
    return instance;
  }
  
  public static void reset() {
    if (instance.isRunning()) {
      instance.stop();
    }
    instance = new StopWatch();
  }
}

Once that is done, its a simple matter of calling the start() and stop() methods on the underlying Stopwatch singleton (shown below in my modified code, in case you need to see it). Based on a run of the JUnit test that I used to test the aggregate AE, I discovered that the maximum time in the analysis is spent within the DictionaryAnnotator. Whats more, the DictionaryAnnotator is called 4 times (with different parameters) in a single pass through the aggregate AE, so improving the performance would probably be time well-spent. Here is the output of the StopWatch call before any changes were made.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
    [junit] StopWatch '': running time (millis) = 21
    [junit] -----------------------------------------
    [junit] ms     %     Task name
    [junit] -----------------------------------------
    [junit] 00000  000%  PatternAnnotator[preserve]
    [junit] 00000  000%  PatternAnnotator[transform]
    [junit] 00013  062%  DictionaryAnnotator[preserve/matchCase]
    [junit] 00000  000%  DictionaryAnnotator[transform/matchCase]
    [junit] 00001  005%  DictionaryAnnotator[preserve/ignoreCase]
    [junit] 00000  000%  DictionaryAnnotator[transform/ignoreCase]
    [junit] 00000  000%  PatternAnnotator[preserve]
    [junit] 00000  000%  PatternAnnotator[transform]
    [junit] 00001  005%  DictionaryAnnotator[preserve/matchCase]
    [junit] 00000  000%  DictionaryAnnotator[transform/matchCase]
    [junit] 00000  000%  DictionaryAnnotator[preserve/ignoreCase]
    [junit] 00000  000%  DictionaryAnnotator[transform/ignoreCase]
    [junit] 00000  000%  PatternAnnotator[preserve]
    [junit] 00000  000%  PatternAnnotator[transform]
    [junit] 00000  000%  DictionaryAnnotator[preserve/matchCase]
    [junit] 00000  000%  DictionaryAnnotator[transform/matchCase]
    [junit] 00000  000%  DictionaryAnnotator[preserve/ignoreCase]
    [junit] 00000  000%  DictionaryAnnotator[transform/ignoreCase]
    [junit] 00000  000%  PatternAnnotator[preserve]
    [junit] 00000  000%  PatternAnnotator[transform]
    [junit] 00000  000%  DictionaryAnnotator[preserve/matchCase]
    [junit] 00001  005%  DictionaryAnnotator[transform/matchCase]
    [junit] 00000  000%  DictionaryAnnotator[preserve/ignoreCase]
    [junit] 00000  000%  DictionaryAnnotator[transform/ignoreCase]
    [junit] 00000  000%  PatternAnnotator[preserve]
    [junit] 00000  000%  PatternAnnotator[transform]
    [junit] 00000  000%  DictionaryAnnotator[preserve/matchCase]
    [junit] 00001  005%  DictionaryAnnotator[transform/matchCase]
    [junit] 00000  000%  DictionaryAnnotator[preserve/ignoreCase]
    [junit] 00000  000%  DictionaryAnnotator[transform/ignoreCase]
    [junit] 00000  000%  PatternAnnotator[preserve]
    [junit] 00000  000%  PatternAnnotator[transform]
    [junit] 00000  000%  DictionaryAnnotator[preserve/matchCase]
    [junit] 00000  000%  DictionaryAnnotator[transform/matchCase]
    [junit] 00001  005%  DictionaryAnnotator[preserve/ignoreCase]
    [junit] 00000  000%  DictionaryAnnotator[transform/ignoreCase]
    [junit] 00000  000%  PatternAnnotator[preserve]
    [junit] 00000  000%  PatternAnnotator[transform]
    [junit] 00000  000%  DictionaryAnnotator[preserve/matchCase]
    [junit] 00000  000%  DictionaryAnnotator[transform/matchCase]
    [junit] 00000  000%  DictionaryAnnotator[preserve/ignoreCase]
    [junit] 00000  000%  DictionaryAnnotator[transform/ignoreCase]
    [junit] 00001  005%  PatternAnnotator[preserve]
    [junit] 00000  000%  PatternAnnotator[transform]
    [junit] 00000  000%  DictionaryAnnotator[preserve/matchCase]
    [junit] 00000  000%  DictionaryAnnotator[transform/matchCase]
    [junit] 00000  000%  DictionaryAnnotator[preserve/ignoreCase]
    [junit] 00000  000%  DictionaryAnnotator[transform/ignoreCase]
    [junit] 00000  000%  PatternAnnotator[preserve]
    [junit] 00000  000%  PatternAnnotator[transform]
    [junit] 00000  000%  DictionaryAnnotator[preserve/matchCase]
    [junit] 00000  000%  DictionaryAnnotator[transform/matchCase]
    [junit] 00001  005%  DictionaryAnnotator[preserve/ignoreCase]
    [junit] 00000  000%  DictionaryAnnotator[transform/ignoreCase]
    [junit] 00000  000%  PatternAnnotator[preserve]
    [junit] 00000  000%  PatternAnnotator[transform]
    [junit] 00000  000%  DictionaryAnnotator[preserve/matchCase]
    [junit] 00000  000%  DictionaryAnnotator[transform/matchCase]
    [junit] 00001  005%  DictionaryAnnotator[preserve/ignoreCase]
    [junit] 00000  000%  DictionaryAnnotator[transform/ignoreCase]
    [junit] 
    [junit] ------------- ---------------- ---------------

If you add up the times for the DictionaryAnnotator (except the very first call, which seems to be the framework lazily initializing the AE on the first call to process), the time spent in the DictionaryAnnotator accounts for 1/3 of the total runtime.

If you look at the code (you can find it in my old post here) its easy to see why it could be a problem. The code to shingle the input is essentially an O(n2) operation - the number of shingles produced for an n-word input is the sum of an arithmetic series (k n-word shingles, k-1 n-1 word shingles, and so on) - the sum is computed using the formula for Sn here. Each of these result in a map lookup of O(1).

On the other hand, using an adjacency map to store the collocated words for multi-word phrases in the dictionary, and scanning the input one word at a time, results in n lookups, each of O(1) for an input string of n words, so the complexity of such an algorithm would be O(n). So definitely there seems to be some scope for savings.

Here is the code for the updated DictionaryAnnotator.

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
// Source: src/main/java/com/mycompany/tgni/uima/annotators/keyword/DictionaryAnnotator.java
package com.mycompany.tgni.uima.annotators.keyword;

import java.io.IOException;
import java.io.StringReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.Stack;

import org.apache.commons.lang.StringUtils;
import org.apache.lucene.analysis.TokenStream;
import org.apache.lucene.analysis.core.LowerCaseFilter;
import org.apache.lucene.analysis.core.WhitespaceTokenizer;
import org.apache.lucene.analysis.tokenattributes.CharTermAttribute;
import org.apache.lucene.analysis.tokenattributes.OffsetAttribute;
import org.apache.lucene.util.Version;
import org.apache.uima.UimaContext;
import org.apache.uima.analysis_component.JCasAnnotator_ImplBase;
import org.apache.uima.analysis_engine.AnalysisEngineProcessException;
import org.apache.uima.jcas.JCas;
import org.apache.uima.resource.ResourceAccessException;
import org.apache.uima.resource.ResourceInitializationException;
import org.springframework.util.StopWatch;

import com.mycompany.tgni.uima.conf.SharedMapResource;
import com.mycompany.tgni.uima.conf.SharedSetResource;
import com.mycompany.tgni.uima.utils.StopwatchHolder;

public class DictionaryAnnotator extends JCasAnnotator_ImplBase {

  private String preserveOrTransform;
  private boolean ignoreCase;

  private Map<String,String> dictMap = new HashMap<String,String>();
  private Map<String,Set<String>> collocMap = new HashMap<String,Set<String>>();
  
  private final static String PRESERVE = "preserve";
  private final static String TRANSFORM = "transform";

  private class Word {
    public String word;
    public int start;
    public int end;
  }

  @Override
  public void initialize(UimaContext ctx) 
      throws ResourceInitializationException {
    super.initialize(ctx);
    preserveOrTransform = (String) ctx.getConfigParameterValue(
      "preserveOrTransform");
    ignoreCase = (Boolean) ctx.getConfigParameterValue("ignoreCase");
    try {
      if (PRESERVE.equals(preserveOrTransform)) {
        SharedSetResource res = (SharedSetResource) 
          ctx.getResourceObject("dictAnnotatorProperties");
        for (String dictPhrase : res.getConfig()) {
          dictMap.put(ignoreCase ? 
            StringUtils.lowerCase(dictPhrase) : dictPhrase, null);
        }
      } else if (TRANSFORM.equals(preserveOrTransform)) {
        SharedMapResource res = (SharedMapResource) 
          ctx.getResourceObject("dictAnnotatorProperties");
        Map<String,String> cfg = res.getConfig();
        for (String dictPhrase : cfg.keySet()) {
          dictMap.put(ignoreCase ? 
            StringUtils.lowerCase(dictPhrase) : dictPhrase, 
            cfg.get(dictPhrase));
        }
      } else {
        throw new ResourceInitializationException(
          new IllegalArgumentException(
          "Configuration parameter preserveOrTransform " +
          "must be either 'preserve' or 'transform'"));
      }
      for (String dictPhrase : dictMap.keySet()) {
        String[] words = StringUtils.split(dictPhrase, " ");
        String prevWord = words[0];
        for (int i = 1; i < words.length; i++) {
          if (! collocMap.containsKey(prevWord)) {
            collocMap.put(prevWord, new HashSet<String>());
          }
          collocMap.get(prevWord).add(words[i]);
          prevWord = "_" + words[i];
        }
      }
    } catch (ResourceAccessException e) {
      throw new ResourceInitializationException(e);
    }
  }
  
  @Override
  public void process(JCas jcas) 
      throws AnalysisEngineProcessException {
    StopWatch watch = StopwatchHolder.instance();
    watch.start(getClass().getSimpleName() + "[" + 
      preserveOrTransform + "/" + 
      (ignoreCase ? "ignoreCase" : "matchCase") + "]");
    try {
      Stack<Word> collocations = new Stack<Word>();
      String text = jcas.getDocumentText();
      WhitespaceTokenizer tokenizer = new WhitespaceTokenizer(
        Version.LUCENE_40, new StringReader(text));
      TokenStream tokenStream = ignoreCase ?
        new LowerCaseFilter(Version.LUCENE_40, tokenizer) : tokenizer;
      while (tokenStream.incrementToken()) {
        CharTermAttribute term = 
          (CharTermAttribute) tokenStream.getAttribute(
          CharTermAttribute.class);
        OffsetAttribute offset = 
          (OffsetAttribute) tokenStream.getAttribute(
          OffsetAttribute.class);
        Word word = new Word();
        word.word = term.toString();
        word.start = offset.startOffset();
        word.end = offset.endOffset();
        if (collocations.isEmpty()) {
          // no previous word in stack
          if (collocMap.containsKey(word.word)) {
            collocations.push(word);
          }
        } else {
          // previous word exists, part of phrase
          Word prevWord = collocations.peek();
          Set<String> nextWords = collocMap.get(prevWord.word);
          if (nextWords != null && nextWords.contains(word.word)) {
            word.word = "_" + word.word;
            collocations.push(word);
          } else {
            // complete phrase or single word found, check dictMap
            Word phrase = getPhrase(collocations);
            annotatePhrase(phrase, jcas);
            collocations.clear();
          }
        }
      }
      // end of input, handle trailing stacked words
      if (! collocations.isEmpty()) {
        Word phrase = getPhrase(collocations);
        annotatePhrase(phrase, jcas);
        collocations.clear();
      }
    } catch (IOException e) {
      throw new AnalysisEngineProcessException(e);
    }
    watch.stop();
  }

  private Word getPhrase(Stack<Word> collocations) {
    List<String> words = new ArrayList<String>();
    Word phrase = new Word();
    phrase.start = collocations.elementAt(0).start;
    phrase.end = 0;
    for (Iterator<Word> it = collocations.iterator(); it.hasNext(); ) {
      Word w = it.next();
      words.add(w.word.startsWith("_") ? w.word.substring(1) : w.word);
      phrase.end = w.end;
    }
    phrase.word = StringUtils.join(words.iterator(), " ");
    return phrase;
  }
  
  private void annotatePhrase(Word phrase, JCas jcas) {
    if (dictMap.containsKey(phrase)) {
      KeywordAnnotation annotation = new KeywordAnnotation(jcas);
      annotation.setBegin(phrase.start);
      annotation.setEnd(phrase.end);
      if (TRANSFORM.equals(preserveOrTransform)) {
        annotation.setTransformedValue(dictMap.get(phrase));
      }
      annotation.addToIndexes();
    }
  }
}

The dictionary terms are loaded into two maps in the initialize() method. The first map (dictMap) is a simple map that contains the word or phrase (for multi-word dictionary terms) on the LHS, and the synonym(s) on the RHS if transform is specified. The second one is the adjacency map (collocMap), that looks something like this in JSON format. Note that the value part is really a Set (for fast containment lookup) even though the notation indicates its a List.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
Dictionary Terms
================
vitamin a deficiency
vitamin d deficiency
canine vitamin k deficiency
sun burn

Equivalent Adjacency Map
========================
collocMap = {
  "vitamin" : [ "a", "d" ], 
  "_a" : [ "deficiency" ], 
  "_d" : [ "deficiency" ], 
  "canine" : [ "vitamin" ], 
  "_vitamin" : [ "k" ], 
  "_k" : [ "deficiency" ], 
  "sun" : [ "burn" ]
}

Only words in phrases are stored in the adjacency map. Words other than head words are prefixed with "_" to prevent the code from matching on partial phrases.

Running the JUnit test against the updated code results in the following timings.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
    [junit] StopWatch '': running time (millis) = 22
    [junit] -----------------------------------------
    [junit] ms     %     Task name
    [junit] -----------------------------------------
    [junit] 00000  000%  PatternAnnotator[preserve]
    [junit] 00000  000%  PatternAnnotator[transform]
    [junit] 00014  064%  DictionaryAnnotator[preserve/matchCase]
    [junit] 00000  000%  DictionaryAnnotator[transform/matchCase]
    [junit] 00001  005%  DictionaryAnnotator[preserve/ignoreCase]
    [junit] 00000  000%  DictionaryAnnotator[transform/ignoreCase]
    [junit] 00000  000%  PatternAnnotator[preserve]
    [junit] 00001  005%  PatternAnnotator[transform]
    [junit] 00000  000%  DictionaryAnnotator[preserve/matchCase]
    [junit] 00000  000%  DictionaryAnnotator[transform/matchCase]
    [junit] 00000  000%  DictionaryAnnotator[preserve/ignoreCase]
    [junit] 00000  000%  DictionaryAnnotator[transform/ignoreCase]
    [junit] 00000  000%  PatternAnnotator[preserve]
    [junit] 00000  000%  PatternAnnotator[transform]
    [junit] 00000  000%  DictionaryAnnotator[preserve/matchCase]
    [junit] 00000  000%  DictionaryAnnotator[transform/matchCase]
    [junit] 00001  005%  DictionaryAnnotator[preserve/ignoreCase]
    [junit] 00000  000%  DictionaryAnnotator[transform/ignoreCase]
    [junit] 00000  000%  PatternAnnotator[preserve]
    [junit] 00000  000%  PatternAnnotator[transform]
    [junit] 00000  000%  DictionaryAnnotator[preserve/matchCase]
    [junit] 00001  005%  DictionaryAnnotator[transform/matchCase]
    [junit] 00000  000%  DictionaryAnnotator[preserve/ignoreCase]
    [junit] 00000  000%  DictionaryAnnotator[transform/ignoreCase]
    [junit] 00000  000%  PatternAnnotator[preserve]
    [junit] 00000  000%  PatternAnnotator[transform]
    [junit] 00000  000%  DictionaryAnnotator[preserve/matchCase]
    [junit] 00000  000%  DictionaryAnnotator[transform/matchCase]
    [junit] 00001  005%  DictionaryAnnotator[preserve/ignoreCase]
    [junit] 00000  000%  DictionaryAnnotator[transform/ignoreCase]
    [junit] 00000  000%  PatternAnnotator[preserve]
    [junit] 00000  000%  PatternAnnotator[transform]
    [junit] 00000  000%  DictionaryAnnotator[preserve/matchCase]
    [junit] 00000  000%  DictionaryAnnotator[transform/matchCase]
    [junit] 00000  000%  DictionaryAnnotator[preserve/ignoreCase]
    [junit] 00000  000%  DictionaryAnnotator[transform/ignoreCase]
    [junit] 00000  000%  PatternAnnotator[preserve]
    [junit] 00001  005%  PatternAnnotator[transform]
    [junit] 00000  000%  DictionaryAnnotator[preserve/matchCase]
    [junit] 00000  000%  DictionaryAnnotator[transform/matchCase]
    [junit] 00000  000%  DictionaryAnnotator[preserve/ignoreCase]
    [junit] 00000  000%  DictionaryAnnotator[transform/ignoreCase]
    [junit] 00000  000%  PatternAnnotator[preserve]
    [junit] 00000  000%  PatternAnnotator[transform]
    [junit] 00000  000%  DictionaryAnnotator[preserve/matchCase]
    [junit] 00001  005%  DictionaryAnnotator[transform/matchCase]
    [junit] 00000  000%  DictionaryAnnotator[preserve/ignoreCase]
    [junit] 00000  000%  DictionaryAnnotator[transform/ignoreCase]
    [junit] 00000  000%  PatternAnnotator[preserve]
    [junit] 00000  000%  PatternAnnotator[transform]
    [junit] 00001  005%  DictionaryAnnotator[preserve/matchCase]
    [junit] 00000  000%  DictionaryAnnotator[transform/matchCase]
    [junit] 00000  000%  DictionaryAnnotator[preserve/ignoreCase]
    [junit] 00000  000%  DictionaryAnnotator[transform/ignoreCase]
    [junit] 00000  000%  PatternAnnotator[preserve]
    [junit] 00000  000%  PatternAnnotator[transform]
    [junit] 00000  000%  DictionaryAnnotator[preserve/matchCase]
    [junit] 00000  000%  DictionaryAnnotator[transform/matchCase]
    [junit] 00000  000%  DictionaryAnnotator[preserve/ignoreCase]
    [junit] 00000  000%  DictionaryAnnotator[transform/ignoreCase]
    [junit] 
    [junit] ------------- ---------------- ---------------

Not much of a change, as you can see, but now the DictionaryAnnotator takes 1/4 of the total processing time in the test set. Figuring that perhaps my JUnit test strings did not exercise the algorithm enough, I then ran the loader (which calls the aggregate AE, and which took 3 weeks to complete the last time I ran it) over 10K concepts (1/100-th of the full dataset), using the old and new codes, and both times the job finished in about 45 minutes.

My conclusion is that O(n2) performance of the old code approximates the O(n) performance of the new code since n is quite small - most of my synonyms are 2-3 words long, with some outliers. So even though the data doesn't show significant improvement in performance, I will make the change anyway, since the new code has better performance characteristics.

Of course, extrapolating the numbers means that I still need 3.12 days to process the full dataset, which is still kind of high. Since the job lends itself well to parallelization, I am going to try doing that next.

Posted by Sujit Pal at 8:45 AM 0 comments

Labels: , , ,

Share/Save: Digg Technorati Delicious StumbleUpon Reddit BlinkList Furl Mixx Facebook Google Bookmark Yahoo

Saturday, June 04, 2011

Java Data Structure: Insertable StringBuilder

This post describes a data structure that was inspired by my younger son's laziness. In an attempt to keep me involved in my children's education, I have been assigned the chore of checking their homework each night when I get back from work. One of these (for my younger son) is a mini book-report (3-4 sentences) for something he has read that day. Invariably, in an attempt to complete his homework as quickly as possible and get back to more important things (like video games), he will construct sentences with missing words in them. When I point them out, he will do something like this:

1
2
3
          is                      up a                      the
This story about Jack. Jack climbed beanstalk. He then killed giant.
          ^                        ^                         ^

Well, perhaps not this bad, but you get the idea.

I have been working recently on a custom Solr component using the Lucene FastVectorHighlighter (some preliminary info here), involving a multi-pass highlighting strategy, where the first group of terms need to be highlighted in one color and the second group in a different color.

On the second pass (as in the first), I need the original source string, so I hit upon the idea of storing the inserts (the "is", "up a" and "the" in the example above) in a separate data structure and merge them in at the end of the processing. Not a hugely complex idea, of course, but one that could be useful to other people with similar needs, so I decided to share it here.

Here is the code for my InsertableStringBuilder class. This exposes the single StringBuilder method I often use (append), and an additional insert method that writes positional inserts into a SortedMap. The toString() method merges the contents of the StringBuilder and the contents of the inserts into a single string.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
// Source: src/main/java/com/mycompany/hilite/InsertableStringBuilder.java
package com.mycompany.hilite;

import java.util.SortedMap;
import java.util.TreeMap;

/**
 * A simple data structure that behaves like a StringBuilder,
 * except you can add inserts into it at specific character
 * positions (0-based) containing strings to be inserted at 
 * these positions. The toString() method will merge the inserts
 * and the string and return the full buffer.
 */
public class InsertableStringBuilder {

  private StringBuilder buf;
  private SortedMap<Integer,String> inserts;
  
  /**
   * Default ctor.
   */
  public InsertableStringBuilder() {
    this.buf = new StringBuilder();
    this.inserts = new TreeMap<Integer,String>();
  }

  /**
   * Ctor to instantiate this object with an input String.
   * @param s the input String to append.
   */
  public InsertableStringBuilder(String s) {
    this();
    this.buf.append(s);
  }

  /**
   * Similar to StringBuilder.append(String). Allows appending
   * strings to the main input String.
   * @param s the String to append.
   */
  public void append(String s) {
    this.buf.append(s);
  }
  
  /**
   * Add an insert string at the specified position. If
   * an attempt is made to insert past the end of the current
   * input String an ArrayIndexOutOfBoundsException will be
   * thrown. If an insert already exists at the requested 
   * position, the replace parameter controls whether the
   * new insert overwrites the older one or is ignored. 
   * @param pos the position to insert into.
   * @param s the insert string.
   * @param replace if true, older insert at this position,
   *        if present, will be replaced by this newer one.
   */
  public void insert(int pos, String s, boolean replace) {
    if (pos > buf.length()) {
      throw new IndexOutOfBoundsException(
        "Can't insert past end of string (pos=" + 
        pos + ", len=" + buf.length() + ")");
    }
    if (! replace) {
      if (! this.inserts.containsKey(pos)) {
        this.inserts.put(pos, s);
      }
    } else {
      this.inserts.put(pos, s);
    }
  }
  
  /**
   * Merges the input String and all the insert Strings
   * to create the merged string.
   * @return the merged string.
   */
  @Override
  public String toString() {
    StringBuilder obuf = new StringBuilder();
    int pos = 0;
    for (int ipos : inserts.keySet()) {
      if (pos < ipos) {
        obuf.append(buf.subSequence(pos, ipos));
      }
      obuf.append(inserts.get(ipos));
      pos = ipos;
    }
    if (pos < buf.length()) {
      obuf.append(buf.subSequence(pos, buf.length()));
    }
    return obuf.toString();
  }
}

Currently I have chosen to only implement the StringBuilder methods I am interested in. I would have preferred to just extend StringBuilder but sadly, it is marked final, so I had to take the containment approach shown above. Of course, if you do need more methods exposed from StringBuilder, it is trivial to expose them by just delegating to the method in the underlying StringBuilder.

Using this class, the merging code in lines 226-245 in the CustomFastVectorHighlighterTest class described in my earlier post changes to:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
      InsertableStringBuilder isb = new InsertableStringBuilder();
      isb.append(StringUtils.substring(
        source, startFragPosition, endFragPosition));
      for (Range termPosition : termPositions) {
        isb.insert(termPosition.getMinimumInteger() - startFragPosition, 
          pretag, false);
        isb.insert(termPosition.getMaximumInteger() - startFragPosition, 
          posttag, false);
      }
      return isb.toString();

There are two things I find rather nice about this class. First, of course, is that it hides the actual (fairly tedious) code to merge inserts in its toString() method. Second, with this class it is now possible to merge inserts from multiple sources into a single string without too much effort.

Posted by Sujit Pal at 11:46 AM 0 comments

Labels: , ,

Share/Save: Digg Technorati Delicious StumbleUpon Reddit BlinkList Furl Mixx Facebook Google Bookmark Yahoo

Saturday, August 15, 2009

Semantic Tag Suggester in Python

Couple of weeks ago, I mentioned how nice it would be if I had a program that suggested "tags" (called Labels in Blogger) for my blog posts, using my existing tags and the content of the post as input. The motivation was to clean up my rather defocused, but nevertheless useful Tag Cloud on the left rail.

I initially thought of rolling up the tags into a set of 10 or so categories, but I like the ability to find an obscure post by clicking on the particular technology, something I would miss with this approach. So the solution I came up with was to keep both, but roll up the obscure tags into larger category tags. In addition, because I often refer to the same thing in slightly different ways, synonymy had to be considered, both for the base tag as well as when rolling it up into one or more categories. So my "dictionary" (full file available here) of tags looks something like this.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
# Source: src/main/resources/blog_dict.txt
# Format:
# Label:Synonyms:Categories
acegi::java,security
actor:actors:concurrent-programming,patterns
actorfoundry::java,concurrent-programming,patterns,actor
ajax::javascript,web-development
algorithms::
annotations::java,programming
ant::java,programming
apache-cxf::java,webservices,soap
apache-solr::java,search,lucene
atom::xml,webservices
...

The fields are separated by the colon character. Label is the only field that is required, synonyms and categories are optional. The original list of labels (the first column) was built using a download of my blogs from Blogger and a few simple Unix commands. The second and third columns are built by hand, and are of course, rather subjective and context-dependent.

The usage of this tool depends a lot on the peculiarities of my blogging habits. Because I write my blog offline and copy-paste it into the Blogger editor tool for upload, I have access to the original text to pass into the script. The script parses the blog into an inverted index of words to positions, then loops through the labels and their synonyms in the dictionary to find the occurrences of these words or phrases. The output is a list of labels sorted in descending order by their frequency.

As before, the logic for parsing the body of the blog post into an inverted index depends on some home-grown markup that I use when writing my blogs. For one, I like to decide the title beforehand, and put it at the first line of my post in HTML <title> tags. I also put code and data inside <pre> tags. So the parsing logic uses the <title> tag marker to count any dictionary phrases TITLE_BOOST times, based on the assumption that the title describes the content quite well. Further, the parser skips (usually multi-line) content between the <pre> tags.

The script is written in Python and initially creates two data structures, the Dictionary and the InvertedIndex. The Dictionary provides methods to return the list of labels, and the synonyms and categories for a given label. The inverted index provides a method to return the occurrence count for a given word or phrase. Here is the script:

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
#!/usr/bin/python
import sys
import getopt
import os.path
import re

### Configuration ###
# path to dict file
DEFAULT_DICT_PATH = "/home/sujit/bin/blog_dict.txt" 
TITLE_BOOST = 5      # score boost for title occurrences
COUNT_CUTOFF = 4     # min count to report a term
### Configuration ###

class InvertedIndex:
  """
  Class to convert the input file into an inverted index of words 
  and their corresponding word positions. The class uses this data 
  structure to return a count of occurrences of single or multi-
  word phrases in the document.
  """
  def __init__(self, inpath):
    self.index = {}
    self.wordSplitter = re.compile(r'[-_]')
    infile = open(inpath, 'r')
    regex = re.compile(r'[;,\.-_\" ]|<[^>].*>')
    pos = 0
    ignorable = False    # words are not counted while this is True
    while (True):
      line = infile.readline()
      if (not line):
        break
      # code blocks start with <pre> and end with </pre>, 
      # which we ignore.
      if (line.startswith("<pre>")):
        ignorable = True
      if (ignorable and line.startswith("</pre>")):
        ignorable = False
      if (ignorable):
        continue
      line = line[:-1].lower()
      words = regex.split(line)
      # make sure phrase matches spanning paragraphs are not considered
      pos = pos + 1
      boost = 1
      if line.startswith("<title>") and 
          line.endswith("</title>"):
        # word matches in title are scored TITLE_BOOST times normal
        # this is done by considering the title line TITLE_BOOST 
        # times, that way, neighboring words are still neighboring 
        # words, but they just "occur" TITLE_BOOST times in the title.
        boost = TITLE_BOOST
      for i in range(0, boost):
        for word in words:
          try:
            positions = self.index[word]
          except KeyError:
            positions = set()
          pos = pos + 1
          positions.add(pos)
          self.index[word] = positions
    infile.close()

  def getCount(self, term):
    words = self.wordSplitter.split(term.lower())
    prevPositions = set()
    newPositions = set()
    for word in words:
      try:
        positions = self.index[word]
        if (len(prevPositions) == 0):
          # the previous positions set is empty, which could only
          # happen if this is the first word in our term. So there
          # is nothing to filter against, so the current positions
          # becomes the basis for the filtering. If it exits at this
          # point, because this is a single word phrase, then this
          # will report success or failure based on the length of
          # positions collection.
          prevPositions.update(positions)
        else:
          # we have a previous position set, so we compare each
          # entry in our current positions to see if it is 1 ahead
          # of an entry in our previous positions, The intersection
          # will form the basis of the previous positions for the
          # next word in the phrase.
          newPositions = positions.intersection(
            map(lambda x: x+1, prevPositions))
          prevPositions.clear()
          prevPositions.update(newPositions)
          newPositions.clear()
      except KeyError:
        return 0
    return len(prevPositions)

class Dictionary():
  """
  Class to encapsulate the creation of a data structure from the 
  dictionary file. Format of the dictionary file is as follows:
  label:label_synonyms:label_categories
  where:
  label = the word or phrase that represents a label. If the label 
          is a multi-word label, it should be hyphenated.
  label_synonyms = a comma-separated list of synonyms for the label. 
          For example, webservice may be used instead of web-service. 
          As in the label field, multi-word synonyms should be 
          hyphenated.
  label_categories = a comma-separated list of categories the label 
          should roll up to. For example, cx_oracle could roll up to
          databases, oracle, python and scripting.
  """
  def __init__(self, dictpath):
    self.cats = {}
    self.syns = {}
    dictfile = open(dictpath, 'r')
    while (True):
      line = dictfile.readline()
      if (not line):
        break
      if (line.startswith("#")):
        # comment line, skip
        continue
      # strip out the line terminator, lowercase and replace all
      # whitespace with hyphen.
      line = line[:-1].lower().replace(" ", "-")
      (label, synonyms, categories) = line.split(":")
      # empty comma-separated synonyms or categories are stored in the
      # cats and syns dictionaries as a empty element, the filter
      # removes it so an empty string maps to an empty list
      self.cats[label] = filter(
        lambda x: len(x.strip()) > 0, categories.split(","))
      self.syns[label] = filter(
        lambda x: len(x.strip()) > 0, synonyms.split(","))
    dictfile.close

  def labels(self):
    """
    Return the list of all labels in the dictionary.
    @return the list of all labels.
    """
    return self.cats.keys()

  def synonyms(self, label):
    """
    Return the synonyms for the specified label. If no synonyms
    exist, returns an empty List.
    @param label the label to look up in the dictionary.
    @return a List of synonyms mapped to the label
    """
    try:
      return self.syns[label]
    except KeyError:
      return []

  def categories(self, label):
    """
    Return the categories for the specified label, If no categories
    exist, returns an empty List.
    @param label the label to look up in the dictionary.
    @return a List of categories mapped to the label.
    """
    try:
      return self.cats[label]
    except KeyError:
      return []
    
def usage(message=""):
  if (len(message) > 0):
    print "Error: %s" % (message)
  print "Usage: %s --help|([--dict=dict_file] --file=input_file)" % 
    (sys.argv[0])
  print "-d|--dict: full path to dictionary file"
  print "-f|--file: full path to input file to be analyzed"
  print "-i|--interactive: prompt for each label and create a label string"
  print "-h|--help: print this information"
  sys.exit(2)

def validate():
  """
  Parses the command line parameters and extracts the relevant info
  from it. Returns a triple of (dictpath, filepath, interactive).
  @return a triple extracted from the command line parameters.
  """
  (opts, args) = getopt.getopt(sys.argv[1:], "d:f:ih",
    ["dict=", "file=", "interactive", "help"])
  dictpath = None
  filepath = None
  interactive = False
  for option, argval in opts:
    if (option in ("-h", "--help")):
      usage()
    if (option in ("-d", "--dict")):
      dictpath = argval
      if (not os.path.exists(dictpath)):
        usage("Dictionary File [%s] does not exist" % (dictpath))
    if (option in ("-f", "--file")):
      filepath = argval
      if (not os.path.exists(filepath)):
        usage("Input File [%s] does not exist" % filepath)
    if (option in ("-i", "--interactive")):
      interactive = True
  if (dictpath == None):
    dictpath = DEFAULT_DICT_PATH
  if (filepath == None):
    usage("Input file must be specified")
  return (dictpath, filepath, interactive)

def addCount(countmap, term, count):
  """
  Adds the count to the term count mapping. If no term count mapping
  exists, then one is created and the count updated.
  @param countmap the map of term to term counts to update.
  @param term the term to update for.
  @param count the term count to update.
  """
  try:
    origCount = countmap[term]
  except KeyError:
    origCount = 0
  countmap[term] = origCount + count

def main():
  (dictpath, inpath, interactive) = validate()
  dictionary = Dictionary(dictpath)
  invertedIndex = InvertedIndex(inpath)
  occurrences = {}
  # grab the basic occurrence counts for the labels and its synonyms
  for term in dictionary.labels():
    termCount = invertedIndex.getCount(term)
    addCount(occurrences, term, termCount)
    for synonym in dictionary.synonyms(term):
      # if synonyms exist, also look for occurrences of the synonyms and
      # add it to the occurrence count for the label
      addCount(occurrences, term, invertedIndex.getCount(synonym))
    for category in dictionary.categories(term):
      # add the updated term count (for base label and all its synonyms)
      # to the category occurrences.
      addCount(occurrences, category, occurrences[term])
  terms = occurrences.keys()
  # filter out terms whose counts are below our cutoff
  terms = filter(lambda x: occurrences[x] > COUNT_CUTOFF, terms)
  # sort the remaining (filtered) terms by their count descending
  terms.sort(lambda x, y: occurrences[y] - occurrences[x])
  if (interactive):
    labels = []
    for term in terms:
      yorn = raw_input("%s (%d) - include[Y/n]? " % 
        (term, occurrences[term]))
      if (yorn == 'n' or yorn == 'N'):
        continue
      labels.append(term)
    print "Labels: %s" % (",".join(labels))
  else:
    for term in terms:
      print "%s (%d)" % (term, occurrences[term])
    print "Labels: %s" % (",".join(terms))
    
if __name__ == "__main__":
  main()

The choice of the default dictionary file and the title boost and minimum word occurrence score cutoffs is dependent on a particular setup, so they are in the Configuration block at the beginning of the script. The code is pretty heavily commented, so I won't bore you trying to describe it here. The interactive mode returns the labels in descending order one by one, and you can opt to keep it or not keep it, based on your judgement.

I ran the script on this post and here is what I got. To the suggested labels, I also added data-structure and algorithms, since apart from the user defined InvertedIndex and Dictionary structures, this also has the very useful Python set structure.

1
2
3
4
sujit@sirocco:$ ./tagsuggest.py --file=/path/to/my/post.txt
python (6)
scripting (6)
Labels: python,scripting

Overall, I think this script is going to be pretty useful for me. The quality of its suggestions is dependent on the content of the dictionary, and is not 100% accurate. Fortunately, since it is interactive, it does not have to be - it just has to be better than my own memory, so it "knows" about tags that I have used but no longer remember.

Posted by Sujit Pal at 1:47 PM 0 comments

Labels: , , ,

Share/Save: Digg Technorati Delicious StumbleUpon Reddit BlinkList Furl Mixx Facebook Google Bookmark Yahoo

Subscribe to: Posts (Atom)