Мотивация, почему автоматы?

При работе в поиске большая часть работы имеет смысл слабо структурированного текста. Например, предположим, у нас есть список из примерно 1000 действительных имен и 100 000 фамилий. Прежде чем вводить данные в поисковое приложение, нам нужно извлечь имена и фамилии из текста произвольной формы.

К сожалению, иногда данные имеют полные имена в формате «LastName, FirstName», например «Turnbull, Doug». В других местах, однако, полные имена перечислены «FirstName LastName», например «Doug Turnbull». Добавьте несколько дополнительных представлений, и разобраться в том, какие строки представляют допустимые имена, становится рутиной.

Это становится особенно проблематичным, когда мы используем их как естественные идентификаторы для поиска или объединения нескольких наборов данных. Каждый набор данных может текстуально представлять естественный идентификатор слегка различающимися способами. Мы хотим захватить представления в нескольких наборах данных, чтобы обеспечить правильную работу нашего объединения.

Итак … Что делать текстовой жокей, когда сталкиваются с такими досадными несоответствиями?

Сначала вы можете подумать «регулярное выражение». К сожалению, нормальное регулярное выражение не может помочь в этом случае. Просто пытаюсь написать регулярное выражение, которое допускает контролируемый словарь из 100 тысяч действительных фамилий, но ничего более нетривиального. Не говоря уже о задаче использования такого регулярного выражения.

Но есть один инструмент, который выглядит многообещающим для решения этой проблемы. Новый Automaton API Lucene 4.0  . Давайте рассмотрим, что может предложить этот API, сначала напомнив себе немного о теории CS.

Теория — Конечные Государственные Автоматы И Ты!

API Lucene Automaton предоставляет способ создания и использования  конечных автоматов (FSA). Для тех, кто не помнит компьютерные науки высшего уровня, FSA является вычислительной моделью, в которой входные символы считываются компьютером — автоматом — для управления конечным автоматом. Конечный автомат — это просто граф с узлами и помеченными направленными ребрами. Каждый узел на графике — это состояние, а каждое ребро — это переход, помеченный потенциальным входным символом. Сопоставляя ребра текущего узла с текущим входным символом, автомат следует ребрам до следующего состояния. Следующий входной символ читается, и на основе переходов нового состояния мы переходим в еще одно состояние, так далее и так далее.

Что еще более важно здесь, FSA — это способ указать  обычный язык . Если мы рассматриваем все входные символы как элементы языка, мы можем использовать FSA, чтобы указать язык и определить, является ли данная входная строка допустимой для языка. Мы делаем это путем обработки входной строки, следуя переходам FSA, пока не достигнем конечного узла. Если мы исчерпаем входные символы в таком узле, то можно сказать, что строка символов соответствует языку. В противном случае мы можем сказать, что входная строка не соответствует языку.

Так, например, на рисунке ниже. Строка «nice», представляющая собой последовательность символов «n», «i», «c», «e», принимается как член языка. Все остальные строки отклоняются:

FSA, определяющий язык, который принимает слово «хороший»

Обычный язык может быть просто набором допустимых строк. Или это может быть что-то более размытое, например  расстояние Левенштейна  или  регулярное выражение, которое, как оказывается, может быть представлено на обычном языке. Но даже более сильно, это может быть объединение, объединение или пересечение всего этого.

На практике — автомат как структура данных

На практике автоматы Lucene полезны в качестве структуры данных, которая соединяет традиционные  Set<> и рукописные регулярные выражения. По сравнению с  HashSet или  TreeSet представлением в памяти (может быть) намного, намного меньше, с очень быстрым поиском. Кроме того, Automata предоставляет вам нечеткие функции, такие как сопоставление регулярных выражений.

Its not a general purpose set replacement, however. For an automaton, the set is all the strings of symbols that match the language. However, due to all the fuzzy matching potentially using “regular expressions” enumerating all the input strings that match the language, that is enumerating the members of the set, is non-trivial and might never terminate. Think about it this way, traversal involves manually traversing a graph, so every node, whether a terminus or not, must be visited. This traversal might never terminate because you could have a * regular expression. So enumerating the strings that match the language will involve infinitely repeating the pattern before the*.

Another factor to consider is that while lookup time and memory usage are much, much smaller when compared to a Set<>, indexing can be very time consuming. For the use case of creating an automaton up front to specify a relatively static language once this isn’t a big deal. But for data structures that change frequently, automatons shouldn’t be the first choice.

When compared to a regular expression, the Automaton lends itself to being able to hold more complex regular languages than the ones you could specify in a traditional regular expression. For example, it would be difficult to specify a regular expression that had 500,000 potential first names followed by 1,000 last names unioned with 1,000 last names, a comma, followed by one of 500,000 first names. That’s Perl that’s not even write only. Automaton’s give you the ability to effectively write an extremely rich and large a “regular expression” in readable code in a way that won’t make generating/parsing such a regular expression a giant chore.

Next, lets see how we actually build a useful automaton

Teh Codez — Building An Automaton

(Note all code below can be found at this github repo)

To show off the API, lets take the example we discussed at the outset. Lets say our language allows two forms of full names “FirstName LastName” and “LastName, FirstName”. For simplicity, lets validate only a set of names. First Names: {“Doug”, “John”} and last names {“Berryman”, “Turnbull”}. So in our world all the valid names are “Doug Berryman”, “Doug Turnbull”, “John Berryman”, and “John Turnbull”. Forms where last name comes first followed by a comma, followed by the first name (ie “Turnbull, Doug”) are also considered valid.

So how do we use the Lucene API to build at Automaton to validate this syntax?

There are two key classes that you’ll use over-and-over for building meaningful automata. First the BasicAutomata class provides static methods for constructing automata out of simple building blocks (in our case individual strings). Second the BasicOperations class provides utility methods for combining Automata into unions, intersections, or concatenations of other automata.

Outside of these two central classes, we can also fold in additional automata from other classes. For example, regular expressions via the RegExp class.

Ok, now lets actually start putting together some code. Lets first look at the form “FirstName LastName”. We want to specify a language that takes any of our first names {“John”, “Doug”}, followed by some number of whitespace characters, then followed by any of our last names {“Turnbull”, “Berryman”}.

Our first piece of code forms the foundation for all of our other automata. One of the basic automata we need to build is simply one built from a set of valid strings. For example, an automaton for last names that says “Turnbull” is valid, “Berryman” is valid, but “Pugh” is not.

As this task is going to be a pretty common, occurrence, we’ll be using this utility function that builds an automaton for accepting only the values from the passed in String array:

/**
 * @param strs
 *   All the strings that we want to allow in the returned language
 * @return
 *   An automaton that allows only the passed in strings
 */publicstaticAutomaton stringUnionAutomaton(String[] strs){Automaton strUnion =null;// Simply loop through the strings and place them in the automatonfor(String str: strs){// Basic building block, make an automaton that accepts a singl// stringAutomaton currStrAutomaton =BasicAutomata.makeString(str);if(strUnion ==null){
            strUnion = currStrAutomaton;}else{// Combine the current string with the Automata for the // previous string, saying that this new string is also valid
            strUnion =BasicOperations.union(strUnion, currStrAutomaton);}}return strUnion;}

Notice how on every iteration, we create an automaton for the current string. The first iteration initializes the resulting automaton(strUnion) to the current string’s automata (currStrAutomaton'). On subsequent iterations, we set the resultingstrUnionto the union ofcurrStrAutomatonand itself. Finally returningstrUnion` as the union of all the strings passed in.

With this building block, we can build up a more complex Automaton for our FirstName LastName form:

/**
 * @param firstNames
 *   Set of allowable first names
 * @param lastNames
 *   Set of allowable last names
 * @return
 *   An automaton that allows FirstName\s+LastName
 */publicstaticAutomaton createFirstBeforeLastAutomaton(String[] firstNames,String[] lastNames){List<Automaton> allAutomatons =newArrayList<Automaton>();// Use our builder to create an automaton that allows all the first names
    allAutomatons.add(stringUnionAutomaton(firstNames));// Add in an Automaton that allows any whitespace by using // the regular expressionRegExp anyNumberOfSpaces =newRegExp("[ \t]+");Automaton anySpaces = anyNumberOfSpaces.toAutomaton();
    allAutomatons.add(anySpaces);// Add in an Automaton that allows all our last names       
    allAutomatons.add(stringUnionAutomaton(lastNames));// Return the concatenation off all these automatonsreturnBasicOperations.concatenate(allAutomatons);}

In this code, we’re building three automata and returning the concatenation of all three. So to be a member of the concatenated automaton’s language, if a string passes the first automaton, then with additional characters passes the second automaton, and finally as characters are exhausted finishes the last automaton, we’ll consider this a valid member of this language.

Note the use of the RegExp class. This class supports basic regular-expression matching and allows us to match one-or-more tabs or spaces in the input.

The LastName, FirstName form is similar:

publicstaticAutomaton createLastBeforeFirstAutomaton(String[] firstNames,String[] lastNames){List<Automaton> allAutomatons =newArrayList<Automaton>();
    allAutomatons.add(stringUnionAutomaton(lastNames));RegExp commaPlusAnyNumberOfSpaces =newRegExp(",[ \t]+");
    allAutomatons.add(commaPlusAnyNumberOfSpaces.toAutomaton());
    allAutomatons.add(stringUnionAutomaton(firstNames));returnBasicOperations.concatenate(allAutomatons);}

The only difference here is we’re validating last names before first and our regex separator now has a comma. Otherwise, this is very similar to the other form.

To finish things off, we simply have to create an automata that takes the union of both forms, allowing strings of either language to be valid in the resulting language:

publicstaticAutomaton createNameValidator(String[] firstNames,String[] lastNames){returnBasicOperations.union(createFirstBeforeLastAutomaton(firstNames, lastNames),
                                 createLastBeforeFirstAutomaton(firstNames, lastNames));}

Woohoo! You should be ready to go! Just keep in mind one or two things when building more complex automata:

Automaton Creation Considerations

One of the things that makes the Automaton special is the potential minimal in-memory representation of the data structure. This gives you powerful lookup capabilities against a complex language with a large vocabulary, but noticeably increases index time when compared to a traditional data structure.

To ensure the minimal representation of an Automaton, its important to note that Lucene may not be always keeping the most optimal representation of the data structure in memory. Without minimizing, you could have problems with lookup speed and will certainly have problems exhausting the jvm heap.

For example, if we said that “Ed” and “Eddy” are valid strings in our language, we might initially have something like:

[]---E--->[]---d---[*]
              \
               ---E--->[]---d---[]---d---[]---y---[*]

Add this up over time, and we end up with a horrendous looking graph that leaves you wondering why anyone would ever bother using Automata!

Part of the secret sauce to Lucene’s Automaton’s is minimizations. Instead of representing the graph as a gnarly web of duplicated gobbly, gook, we can perform the minimization operation on the graph above to be simply:

[]---E--->[]---d---[*]
                            \
                             d---[]---y---[*]

By periodically calling Automata.minimize you can reduce the memory footprint of your automaton.

You can track roughly how big your automaton is getting withAutomata.getNumberOfStates() and Automata.getNumberOfTransitions. Its generally a good idea to keep an eye on the size of your automaton and deal with any bloat that occurs during indexing.

Hack Away!

I hope you’ve enjoyed this tutorial, hack away and let me know what you think! I hope to follow up with more information on how to more efficiently create and store automata and delve into their sister library in Lucene —Finite State Transducers!