Compiling a custom dictionary for Kuromoji and Solr

The user dictionary functionality of Solr's Kuromoji tokenizer is extremely useful and easy to use, but it isn't always the right tool for the job. In my case, I'm migrating our system off of the MeCab tokenizer. MeCab also allows you customize the tokenization, but the two models are completely different. In Kuromoji's user dictionary, you take an untokenized phrase and provide the custom tokenization. In MeCab, you just supply a list of words to augment its dictionary. The only way to migrate MeCab's custom dictionary to Kuromoji's user dictionary is by hand.

Fortunately, Kuromoji uses the same base data set as MeCab to build its statistical model for tokenization, and all the data in the base data set is in the same format as the custom MeCab dictionary. Getting Kuromoji to use the custom MeCab dictionary just requires recompiling Kuromoji's dictionary. Figuring out how to do this was surprisingly painless.

In order to compile your new dictionary, you will need...

1. A copy of the MeCab-IPADIC data
2. A copy of the Solr source code
3. A Solr distribution of the same version as your source code
4. A servlet container in which to run Solr

Download MeCab-IPADIC

A tarball of the MeCab dictionary can be downloaded from SourceForge at the following link.

http://sourceforge.net/projects/mecab/files/mecab-ipadic/2.7.0-20070801/

Unpack the tarball to a directory of your choice. From now on I will be referring to this directory as the "dictionary source" directory, or as $DICTSRC in code examples. If you look inside the dictionary source directory, you will see several CSV files. These files use the EUC-JP character encoding scheme. Any custom dictionary will need to be in the same format.

If you open up one of the CSV files, you will see something like this.

いっぽう,555,555,5224,接続詞,*,*,*,*,*,いっぽう,イッポウ,イッポー

そもそも,555,555,4784,接続詞,*,*,*,*,*,そもそも,ソモソモ,ソモソモ

では,555,555,5262,接続詞,*,*,*,*,*,では,デハ,デワ

そういや,555,555,5420,接続詞,*,*,*,*,*,そういや,ソウイヤ,ソーイヤ

かたや,555,555,5368,接続詞,*,*,*,*,*,かたや,カタヤ,カタヤ

The data in each field is roughly as follows.

Field 1 - A word to be used for tokenization

Field 2 - Left cost

Field 3 - Right cost

Field 4 - Word cost

Fields 5-10 - Part of speech

Field 11 - Base form

Field 12 - Reading

Field 13 - Pronunciation

Fields 2, 3, and 4 have to do with the statistical model for tokenization. For the purposes of constructing your custom dictionary, treat fields 2 and 3 as magic numbers mapping to part of speech. Column 4 is the "cost" of the word itself. The lower the cost of the word, the more likely it is to be used in a tokenization. Fields 5-10 should be copied from the appropriate MeCab CSV files. I don't know enough about Japanese to know the differences between fields 11, 12, and 13.

Once you have your custom dictionary ready, drop it into the dictionary source directory along with the rest of the MeCab CSV files.

Set up Solr

Set up your servlet container and deploy the Solr WAR file. Make sure that your servlet container expands the war file so that you can access its contents. The expanded Solr webapp directory will be referred to as $WEBAPP. If the directory $WEBAPP/WEB-INF/classes does not exist, create it.

Open a terminal and find the Solr source code you downloaded. This directory will be referred to as $SOLRSRC. Run the following commands.

> cd $SOLRSRC/lucene/analysis/kuromoji

> ant compile-tools

Compile your dictionary

At this point, we should have everything necessary to compile the custom dictionary. Run the following commands.

> cd $SOLRSRC/lucene/build/analysis/kuromoji/classes/tools/
> java -cp ".:$WEBAPP/WEB-INF/lib/*" \
org.apache.lucene.analysis.ja.util.DictionaryBuilder \
ipadic $DICTSRC $WEBAPP/WEB-INF/classes euc-jp false

Once this completes, you can inspect the files that it created in $WEBAPP/WEB-INF/classes. There will be a deep hierarchy of directories, and then nine binary files that make up your dictionary. One of the JAR files in the lib directory contains a set of files with the same names as these, but the Java servlet spec says that the servlet container should first look in the classes directory, then look in the lib directory. Having your dictionary in the classes directory will override the dictionary packaged with your Solr distribution.

You should now have a Solr instance with a custom Japanese dictionary for tokenization. Start up your servlet container and test it out.

Custom Japanese tokenization in Solr 4.0

Solr 4.0 (really, it's been there since 3.6) has a new analysis module for handling Japanese, called Kuromoji. Kuromoji was developed by Atilika, Inc., who donated it to Solr. I don't speak Japanese myself, but I've been doing some preliminary tests with a Japanese coworker, and it seems to work fairly well.

However, it's not perfect. It will miss an occasional phrase, and is especially problematic with domain specific phrases. To get around this, the Japanese tokenizer accepts a user dictionary, where you can list custom tokenizations. Unfortunately, I couldn't find any documentation on the format for the user dictionary. Fortunately, there is a sample user dictionary in the unit tests for the Japanese tokenizer.


# Custom segmentation for long entries
日本経済新聞,日本 経済 新聞,ニホン ケイザイ シンブン,カスタム名詞
関西国際空港,関西 国際 空港,カンサイ コクサイ クウコウ,テスト名詞

# Custom reading for sumo wrestler
朝青龍,朝青龍,アサショウリュウ,カスタム人名

# Silly entry:
abcd,a b cd,foo1 foo2 foo3,bar
abcdefg,ab cd efg,foo1 foo2 foo4,bar


It's a fairly straight forward CSV format. A hash character (#) starts a comment that continues to the end of a line. Empty lines are ignored. Each non-empty line has four fields separated by commas. After some testing, I was able to figure out what each field in the CSV was.

1. Untokenized phrase
2. Tokenized phrase
3. Reading, or pronunciation
4. Part of speech

There are a couple particulars you need to be aware of when putting together your user dictionary.

Every field is required - If you do not have all four fields your core will not load properly.

Tokenized phrase and reading - These fields are lists of words delimited by spaces. It is important that both the tokenized phrase and the reading have the same number of words. If you don't have this, your core will not load properly.

Spaces around commas - The CSV parser is very picky about format. You should never have any spaces surrounding the commas separating fields. Your core may or may not load, but can get other strange errors during tokenization.

I haven't tested this extensively, but I don't believe there is any way to escape a comma or a hash character. The CSV parser will accept fields surrounded by quote marks, but putting a comma or hash inside a quoted string does not seem to change how it is interpreted. Fortunately, this seems like it would be a very rare use case.

Grokking Solr Trie Fields

I've been trying to wrap my head around Solr's trie field types for the past week, and finally made a break through.

Trie

The first thing you need to understand is the idea of a trie data type. Here's a basic outline of the data structure. Let's say you want to index the following list of words.

bad

bag

bar

bin

bit

We can arrange these words in a tree structure as follows.

b--a--d

|  |

|  |--g

|  |

|  \--r

|

\--i--n

   |

   \--t

To reconstruct one of the words you start at the root node of the tree, and work your way towards a leaf node, keeping track of the letters you encounter along the way. Depending on what you're using the trie data structure for, you may store some piece of data in one of the leaf nodes. If you want more information about the trie data structure, I will refer you to the Wikipedia page, which is fairly complete and easy to understand.

Solr's version of the trie

Another term for a trie is a "prefix tree". Solr uses this idea of prefixes to index numbers so that it can perform range queries efficiently. Just like we can organize words into tries, we can also organize numbers into tries.

Let's say I want to index the integer 3735928559. For clarity, let's rewrite that in hexadecimal, 0xDEADBEEF. When we index this using a TrieIntField, Solr stores the integer four times at different levels of precision.

0xDE000000

0xDEAD0000

0xDEADBE00

0xDEADBEEF

What Solr is doing here is constructing numbers with different length prefixes. This would be equivalent to a trie with this structure.

DE--AD--BE--EF

The reason that this allows for fast range queries is because of what the prefixes represent. The prefixes represent a range of values. It might be better to think of them indexed like this, instead.

0xDExxxxxx

0xDEADxxxx

0xDEADBExx

0xDEADBEEF

Each "x" represents an unset digit. That means the entry 0xDEADxxxx represents every number from 0xDEAD0000 to 0xDEADFFFF. You can get a better feel for this if you play around in the analysis section of the Solr admin console.

Precision Step

The option to set the precision step was the part that I understood the least. The available documentation is rather dense and unhelpful. The precision step lets you tune your index, trading range query speed for index size. A smaller precision step will result in a larger index and faster range queries. A larger precision step will result in a smaller index and slower range queries.

In the example above, I was using a precision step of 8, the default. What the precision step means is how many bits get pruned off the end of the number. Let's see what would happen if we indexed 0xDEADBEEF with a precision step of 12.

0xDExxxxxx

0xDEADBxxx

0xDEADBEEF

And here with a precision step of 4.

0xDxxxxxxx

0xDExxxxxx

0xDEAxxxxx

0xDEADxxxx

0xDEADBxxx

0xDEADBExx

0xDEADBEEx

0xDEADBEEF

As you can see, compared to the default precision step of 8, a precision step of 4 doubled the number of entries in the index. The way it speeds up range searches is by allowing better granularity. If I wanted to search for the documents matching the range 0xDEADBEE0 to 0xDEADBEEF with the default precision step, I would have to check all 16 records in the index and merge the results. With the precision step of 4, I can check the one record for 0xDEADBEEx and get the results I want.

That's a bit of a cherry picked example, but arbitrary range queries will be faster. How that works is left as an exercise for the reader.

May 5, 2015 - I originally thought that the trie data type was not supported directly by Lucene, but this is incorrect. Tokenization of numeric types into the various prefixes is the default behavior of Lucene when indexing numbers.

Custom Solr token filter factories with arguments

Many of the token filter factories, tokenizer factories, and char filter factories that come bundled with Solr accept parameters from a schema.xml. The documentation for writing your own filters and tokenizers doesn't include any details for how to access these parameters, but it's pretty easy to figure out by inspecting the source code for one of the included factories.

The MappingCharFilterFactory takes a path to a file as a parameter. The Javadoc for the MappingCharFilterFactory shows the declaration to put in schema.xml.

<charFilter class="solr.MappingCharFilterFactory" mapping="mapping.txt"/>

In the source code for the MappingCharFilterFactory we can find the following line.

mapping = args.get("mapping"); 

Looking through the class hierarchy, all token filter factories, tokenizer factories, and char filter factories are descendants of AbstractAnalysisFactory where args is declared as a protected variable. All you have to do access the parameters passed from schema.xml is access the args map. args can also be accessed via the getArgs() function.

Solr 4.0 and the BaseTokenFilterFactory

At work, we're upgrading from an ancient version of Lucene to the shiny new Solr 4.0. Unfortunately, the documentation on the Lucene wiki hasn't quite caught up with the most recent version of the software. I would fix omissions like this as I found them, but the wiki does not seem to accept public edits.

There were three classes in Solr 3.6 for creating custom analyzers. Those classes were the BaseCharFilterFactory, BaseTokenizerFactory, and the BaseTokenFilterFactory. These three classes were in the documented package, org.apache.solr.analysis, through Solr 4.0 ALPHA, but as of the BETA release, they have been moved and renamed.

In Solr 4.0, the new classes are the CharFilterFactory, TokenizerFactory, and TokenFilterFactory. They can be found in the org.apache.lucene.analysis.util package, which is part of Lucene's analyzers-common project

Handy links:

• Javadocs
• Source code

Thanks to comment 7 for pointing this out.

Close, but no cigar

Anita Sarkeesian is the author of Feminist Frequency, a blog where she writes and makes videos about the portrayal of women in popular culture. She has made a couple of posts analyzing movies using the Bechdel Test. The Bechdel Test first appeared in the comic Dykes to Watch Out For by Alison Bechdel. The test lays out three simple rules as follows. To pass the test, a movie must...

1. Have two female characters...
2. Who talk to each other...
3. About something other than a man.

The good parts

In Sarkeesian's latest post about the Bechdel test, The Oscars and the Bechdel Test, she uses the test on the 2011 Oscar nominees. On the whole, Sarkeesian does a good job of analyzing the movies and applying the test in a sensible manner. For example, she notes that the Bechdel Test was not originally conceived of as a serious metric.

Let’s remember that this was made as a bit of a joke to make fun of the fact that there are so few movies with significant female characters in them. The reason the test has become so important in recent years is because it actually does highlight a serious and ongoing problem within the entertainment industry.

I also agree with her analysis of how application of the Bechdel Test can be useful.

Again, to be clear this test does not gauge the quality of a film, it doesn’t determine whether a film is feminist or not, and it doesn’t even determine whether a film is woman centered. Some pretty awful movies including ones that have stereotypical and/or sexist representations of women might pass the test with flying colours. Where really well made films that I would highly recommend might not.

She goes on to note that the Bechdel Test is most informative used in aggregate when applied to a group of films. Her choice to use the 2011 Oscar nominees is also good, as it lessens the chance of selection bias.

The Rest

Unfortunately, with all the good things she has to say, her post has one major flaw that undermines any conclusions that can be drawn from her analysis.

In response to the Bechdel Test, I’m often asked, well, what about the reverse? “Why isn’t there also a test to determine if two men talk to each other about something other then a woman”. The answer to that is simple, the test is meant to indicate a problem, and there isn’t a problem with a lack of men interacting with one another.  The Bechdel test is useful because it can point out an institutional pattern and since there’s no problem with men and men’s stories being underrepresented in films, the reverse test is not useful or relevant.

Her dismissal of a Reverse Bechdel Test is very misguided. In fact, not only is the Reverse Bechdel Test relevant, I'll go even further and say that the Bechdel Test is useless without it. To demonstrate this, let me give you a similarly flawed analysis of labor statistics.

Historically, women have been under represented in technical positions, such as engineers and medical doctors. Unfortunately, these problems persist even today. According to the United States Bureau of Labor Statistics, in 2011 there were only 198,000 female software developers in the United States. There are similarly paltry numbers in psychology, with only 140,000 female psychologists during 2011.

Anyone should be able to see the obvious flaw in this paragraph. I've omitted the number of men working in these disciplines. Let's apply the same logic here that Sarkeesian used to dismiss the Reverse Bechdel Test.

What about the number of men in these disciplines? The answer to that is simple, these statistics are meant to indicate a problem, and there isn't a problem with lack of men in these fields. These statistics are useful because it can point out an institutional pattern, and since there's no problem with men being underrepresented in these fields, the number of men in these fields is not useful or relevant.

Unfortunately, this reasoning fails to support its conclusions when you look at all the relevant data. It is true that women are underrepresented among software developers. Compared to the 198,000 women working as software developers, there are over 840,000 men working as software developers. However, it is not the case at all that women are underrepresented among psychologists. While there are 140,000 female psychologists, there are only 56,000 male psychologists. That comes to women making up 19% and 71% of these fields respectively.

"Ah, ha!" you might say, "But Sarkeesian has already accounted for this. She notes that 2 out of 9 movies clearly pass the Bechdel test. That's only 22%."

The problem here is that she is comparing the wrong things. That 22% is a ratio between those movies that pass the test and those that do not. This would be equivalent to comparing the number of women who are psychologists and the number that are not. Of course, this is silly, which is why we compare the number of psychologists that are women to the number of psychologists that are men. Similarly, to make sense of the Bechdel Test, we need to compare the number of movies that pass the test against the number of movies that pass same test with the genders reversed.

If you are still not conviced that the Reverse Bechdel Test is relevant, then I have one simple question for you. What percentage of movies should pass the Bechdel Test, and how do you arrive at that number?

Postscript

For the sake of clarity, I'd like to follow up with a couple points.

First, the two employment statistics I selected were clearly cherry picked. I selected one where women were in the clear minority, and another where they were in the clear majority. This was so I could demonstrate that while a flawed analysis can't affirm a position, neither can it disprove it either. My use of these statistics should not be misconstrued to say anything about representation of women in the work force in general. If you look at all the statistics, it's clear that women are still underrepresented in STEM fields. It certainly took a while for me to find a suitable statistic with women in the majority.

Second, this post is only to point out that Sarkeesian's conclusion is unsupported by her methods, not that her conclusion is necessarily wrong. In fact, I expect that her conclusion is entirely correct. However, without a proper analysis we have no way to accurately assess whether progress towards equality is being made, and if so, how much. We also won't have a good way of determining when the problem has been fixed.

Update: It seems I'm not the first to notice this problem. Ryan over at Mad Art Lab already covered this several months ago.

Another shell script to share

At home I get a lot of use out of the tree command line utility. It gives me a quick and easy way to look at a nested directory structure without having to leave the command line. The computers at work don't have the tree utility, and every so often I really miss it.

So, I wrote my own.

Here's a bash script that is a simplified version of the tree utility.

#!/bin/bash

tree() {
    local prefix=$1
    local dir=$2
    local count=`ls -l $dir | wc -l`
 
    if [[ $count -eq 0 ]]
    then
        return
    fi
 
    local i=1
    local bar="|"
    local nextPrefix="|   "
 
    for file in "$dir"/*
    do
        i=$(($i + 1))
        if [[ $i -eq $count ]]
        then
            bar="\`"
            nextPrefix="    "
        fi
        filename=$(basename $file)
        echo "$prefix$bar---$filename"
        if [[ -d $file ]]
        then
            tree "$prefix$nextPrefix" $file
        fi
    done
}


if [[ -z $1 ]]
then
    dir=`pwd`
else
    dir=$1
fi

if [[ ! -e $dir ]]
then
    echo "Directory $dir does not exist"
    exit 1
elif [[ ! -d $dir ]]
then
    echo "$dir is not a directory"
    exit 2
fi

basename $dir
tree "" $dir