Способы представления словарей для автоматической обработки текстов

    Автоматический анализ текстов практически всегда связан с работой со словарями. Они используются для морфологического анализа, выделения персон (нужны словари личных имен и фамилий) и организаций, а также других объектов.

    В общем виде словарь — множество записей вида {строка, данные ассоциированные с этой строкой}.

    Например, для морфологического анализа словарь состоит из троек {словоформа, нормальная форма, морфологические характеристики}. При анализе слова «мыла» из предложения «мама мыла раму» надо уметь получать следующие варианты анализа:
    Нормальная форма Характеристики
    МЫЛО S (существительное), РОД (родительный падеж), ЕД (единственное число), СРЕД (средний род), НЕОД
    (неодушевленность)
    МЫЛО S (существительное), ИМ (именительный падеж), МН (множественное число), СРЕД (средний род), НЕОД (неодушевленность)
    МЫЛО S (существительное), ВИН (винительный падеж), МН (множественное число), СРЕД (средний род), НЕОД (неодушевленность)
    МЫТЬ V (глагол), ПРОШ (прошедшее время), ЕД (единственное число), ИЗЪЯВ (изъявительное наклонение), ЖЕН (женский род), НЕСОВ (несовершенный вид)



    Хеш-таблицы


    На первый взгляд все просто. Надо использовать хеш-таблицу и дело с концом. Когда словарь маленький это решение очень просто и эффективно.

    Однако, например, морфологический словарь русского языка содержит около 5 млн. словоформ. Получается, что:
    • Надо хранить эти 5 млн. словоформ
    • Для каждой словоформы должна быть ссылка на множество наборов морфологических характеристик
    • Для каждой словоформы хранить ее начальную форму

    Такой способ организации данных является неэкономным, поскольку, во-первых, слова склоняются в основном регулярно, и, во-вторых, в случае русского языка в рамках одного словарной статьи можно выделить подгруппы словоформ, в которых сама форма изменяется незначительно, или не изменяется совсем.

    Например, слово «стена»:
    • ед. ч: «стена»[им], «стены»[род], «стене»[дат], «стену»[вин], «стеной»[твор], «стеною»[твор], «стене»[предл];
    • мн. ч: «стены»[им], «стен»[род], «стенам»[дат], «стены»[вин], «стенами»[твор], «стенах»[предл].

    Видно, что изменяется только окончание, но в хеш-таблице надо хранить слово целиком.

    Можно раздельно храненить основы (неизменяемых частей) и окончания, но в этом случае усложняется проверка слова.

    От префиксного дерева к конечным автоматам


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

    По сравнению с хеш-таблицами, более компактным представлением является префиксное дерево (trie):



    Важное замечание — на рисунках не будут показываться наборы признаков, ассоциированные с каждым конечным узлом дерева (или состоянием конечного автомата). Например, на рисунке узел 6, куда мы попадем по строке «стены» на самом деле будут 3 разбора:
    • единственное число, родительный падеж;
    • множественное число, именительный падеж.;
    • множественное число, винительный падеж.


    Префиксное дерево можно рассматривать как конечный автомат.

    В автомате есть три вида состояний:
    • Начальные — те, с которых начинается работа с автоматом. В детерминированном автомате такое состояние одно, но в недетерминированном их может быть несколько. На рисунках это крайнее левое состояние с номером 0.
    • Финальные — такие состояния, достижение которых означает, что такое слово в словаре есть. Они обозначаются двойным кругом
    • Простые состояния, которые не являются ни начальными, ни финальными

    В дальнейшем будут использоваться обозначения:
    • строка обозначается как w
    • w[i] — i-тый символ данного слова (начиная с 0).
    • s[i] — i-тый узел дерева (или состояние автомата), состояния нумеруются неотрицательными целыми числами, так же будем считать, что s[0] — начальное состояние.
    • s[i][j] — переход из состояния s[i] по символу j. Считаем, что если переход есть, то такое выражение вернет номер состояния, если нет — то вернет -1.


    Приведу базовые алгоритмы для префиксного дерева/конечного автомата.:

    // вычислить префикс строки в автомате
    // и вернуть последовательность (путь) состояний
    int[] prefix(w) {
        int[] stateList;
        // сохраняем и начальное состояние в пути обхода префикса
        stateList[0] = 0;
        int current = 0;
    
        for(int i = 0; i < length(w); i++) {
            int next = s[current][w[i]]
    
            // если перехода нет, то выход
            if(next == -1)
                break;
    
            stateList[i+1] = next;
        }
        
        return stateList;
    }
    
    // добавить суффикс к заданному состоянию 
    // и добавить состояния префикса к stateList
    void addSuffix(w, int[] stateList) {
        // получить последнее состояние из пути обхода префикса
        int current = stateList[length(stateList) - 1];
    
        for(int i = length(stateList) - 1; i < length(w); i++) {
            // добавляем новое состояние в автомат
            int newState = addState();
            // добавить новый переход
            s[current][w[i]] = newState;
            current = newState;
            // сохраним состояние в пути обхода
            stateList[i + 1] = current;
        }
    
        // установка признака финальности для s[current]
        setFinal(current);
    }
    
    // добавить новую строку в trie
    void add(w) {
        // найти максимальный общий префикс
        int[] prefixStates = prefix(w);
        // добавить оставшийся суффикс в автомат
        addSuffix(w, prefixStates)
    }
    


    Представление префиксного дерева как конечного автомата обладает важными свойствами:
    • такой автомат детерминирован — из каждого состояния возможно не более одного перехода по некоторому символу
    • в нем нет циклов — при любом способе обхода автомата никакое состояния не посещается более одного раза.

    Такой специальный автомат называется DAFSA (deterministic acyclic finite state automaton).

    Надо сделать еще одно важное замечание. Для удобства представления и для практического использования будем считать, что состояние описывается не только таблицей переходов, но и данными о финальности состояния. И будем считать, что состояние финально, если в нем такие данные есть, и нет — если они отсутствуют.

    Минимальные конечные автоматы


    Использование префиксных деревьев позволяет избавиться от избыточности префиксов. Фактически это означает, что сокращается объем для хранения неизменяемой части слова. Однако, например, в русском языке окончания слова изменяются в основном регулярно.

    Например, слова «стрела» и «стена» изменяются одинаково:

    СТЕНА: ед. ч: «стена»[им], «стены»[род], «стене»[дат], «стену»[вин], «стеной»[твор], «стеною»[твор], «стене»[предл]; мн. ч: «стены»[им], «стен»[род], «стенам»[дат], «стены»[вин], «стенами»[твор], «стенах»[предл].

    СТРЕЛА: ед. ч: «стрела»[им], «стрелы»[род], «стреле»[дат], «стрелу»[вин], «стрелой»[твор], «стрелою»[твор], «стреле»[предл]; мн. ч: «стрелы»[им], «стрел»[род], «стрелам»[дат], «стрелы»[вин], «стрелами»[твор], «стрелах»[предл].



    Видно, что состояния 4 и 17, с которых начинаются окончания, у обоих слов эквивалентны. Очевидно, что слов с одинаковыми правилами словоизменения в словаре будет много. А значит можно существенно сократить число состояний.

    Собственно, в теории автоматов есть понятие о минимальном автомате – таком автомате, который содержит минимально возможное число состояний, но был бы эквивалентен данному.

    Например, для приведенного выше автомата, минимальный выглядит вот так:


    Существуют и алгоритмы минимизации конечных автоматов, но все они обладают существенным недостатком — для их работы необходимо построить сначала неминимизированный автомат.

    Другим, менее очевидным недостатком, является то, что построенный минимальный автомат не так просто изменять. К нему не подходит простая процедура добавления нового слова, которая используется для префиксного дерева.

    Например, мы построили автомат для слов «fox» и «box», а потом минимизировали его.



    Если в этот автомат добавить без полного перестроения слово «foxes», то получится следующая картина:



    Получается, что в месте с «foxes» добавилось и «boxes», которое мы не добавляли.

    В результате схема использования классических алгоритмов минимизации следующая: при любом изменении словаря необходимо:
    • Построить префиксное дерево (или дополнительно хранить)
    • Минимизировать автомат

    Если словарь большой, то эти процедуры могут занимать значительное время и объем памяти.

    Инкрементальная минимизация детерминированных ацикличных конечных автоматов


    Решение трудностей с минимизацией автоматов представлено в работе: Jan Daciuk; Bruce W. Watson; Stoyan Mihov; Richard E. Watson. «Incremental Construction of Minimal Acyclic Finite-State Automata». В ней представлен алгоритм инкрементальной минимизации детерминированных ацикличных конечных автоматов. Он позволяет изменять уже построенный минимальный автомат. В результате не надо строить полный автомат, а затем его минимизировать.

    Опять рассмотрим наш автомат СТЕНА+СТРЕЛА:


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

    Например, при обходе строки «стрелой» получим следующую последовательность состояний [0, 1, 2, 14, 15, 4, 9, 10].

    Другим важным понятием этого алгоритма является число переходов в заданное состояние (confluence). Если число переходов более одного, то изменять такое состояние небезопасно. На рисунке это состояние 4: у него 2 входящие стрелки.

    Кроме того, алгоритм предполагает, что существует реестр состояний, который позволяет быстро получить состояние, равное данному.

    В результате алгоритм добавления слова w выглядит так:
    void addMinWord(w) {
        // найти максимальный префикс w и сохранить его состояния
        int[] stateList = commonPrefix(w); 
    
        // найти первое состояние с более одним входящим переходом
        int confIdx = findConfluence(stateList);
    
        // клонировать его и все последующие состояния
        if(confIdx > -1) {	
             int idx = confIdx;
    
            while(idx < length(stateList)) {
                int prev = stateList[idx - 1];
                int cloned = cloneState(stateList[idx]);
                stateList[idx] = cloned;
                // после клонирования самого состояния
                // нужно заменить переход с предыдущего на клонированное
                s[prev][w[idx - 1]] = cloned;
                idx++;
                confIdx++;
            }
        }
        // добавить суффикс
        addSuffix(w, stateList);
    
        // заменить состояния строки теми, что есть в реестре. 
        //Если их нет, то добавить в реестр
        replaceOrRegister(w, nodeList);
    }
    
    void replaceOrRegister(w, int[] stateList) {
        int stateIdx = length(stateList) - 1;
        int wordIdx = length(w) - 1;
        
        // обходим состояния строки с конца
        while(stateIdx > 0) {
            int state = stateList[stateIdx];
            // получить из реестра состояние, равное state
            int regState = registerGet(state); 
    
            if(regState == state) { 
                    // если в реестре state уже есть, то переходим к предыдущему
                    continue;  
                } else if(regState == -1) {
                    // если состояния в реестре нет, то добавим его в реестр
                    registerAdd(state);
                } else { 
                    // основная часть, когда в реестре есть состояние, равное state
                    int in = w[wordIdx];
                    // корректируем переход
                    s[stateList[stateIdx - 1]][in] = regState; 
                    // заменяем состояние в пути обхода
                    stateList[stateIdx] = regState; 
                    // удаляем замененное состояние из автомата
                    removeState(state);  
                }
            wordIdx--;
            stateIdx--;
        }
    }
    


    Иллюстрация работы алгоритма



    Рассмотрим простой случай, когда финальность состояние — бинарный признак. Состояние или финально, или нет.

    Автомат для строки «fox».

    Видно, что автомат минимальный, в реестре находятся все состояния [0,1,2,3]

    Добавим к нему слово «box». Поскольку у них нет общего префикса, то добавляем всю строку как суффикс. В результате получим:


    Можно заметить что состояния 3 и 6 равны. Заменим 6 на 3:


    Теперь видно, что равны 2 и 5. Заменим 5 на 2:


    А теперь видно, что равны 1 и 4. Заменим 4 на 1:


    Добавим строку «foxes». При вычислении префикса нашли, что состояния [0, 1, 2, 3] — путь префикса.
    Кроме того, обнаружили, что в состояние 1 входит более одного перехода. Как результат — надо клонировать состояния 1, 2 и 3 по пути обхода слова «fox», поскольку если просто добавить «foxes» к предыдущему автомату, то будет распознаваться строка «boxes», которую мы не задавали.



    Теперь добавим «boxes»:



    При добавлении «boxes» автомат стал меньше. Это на первый взгляд неожиданное поведение, когда при добавлении новых строк автомат в действительности уменьшается. Есть и обратное поведение — когда при удалении строки автомат увеличивается.

    Для правильной работы алгоритма важно корректно реализовать работу с реестром. Состояние удаляется из реестра при любом его изменении таблицы переходов состояния и признака финальности.

    Кроме того, в отличие от обычного множества или таблицы, в добавление/удаление из реестра оперирует точно этим состоянием, а запрос делается на равное.

    Практические использование


    Представленный алгоритм используется в проекте АОТ и в системе ЭТАП-3 для организации быстрого морфологического анализа. При использовании конечных автоматов достигается скорость анализа порядка 1-1.5 млн. слов в секунду. При этом размер автомата без особых ухищрений умещается в 8 Мб.

    Ранее описывалось хранение данных строки как признак финальности. Рассмотрим этот подход более подробно.

    Хранение данных в состоянии автомата



    Подход предполагает, что данные строки рассматриваются как некий атомарный объект. Это в свою очередь накладывает ограничения на эффективность минимизации автомата.

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

    Для морфологического анализа в качестве ассоциированных данных можно использовать наборы морфологических характеристик. Это хорошо работает, поскольку таких наборов мало относительно общего количества словоформ. Например в русском языке в зависимости от принятой модели число таких наборов 500-900. А словоформ 4-5 млн.

    Однако, эффективность минимизации сходит на нет, если в добавок к характеристикам сохранять и полную нормальную форму. Это происходит потому, что пара {нормальная форма, морфологические характеристики} практически уникальна.

    В системе ЭТАП-3 используется именно такой подход для хранения морфологической информации. В самом автомате хранятся только наборы морфологических признаков. А для хранения нормальной формы используется следующий трюк. На этапе построения автомата в качестве входного символа используется не один знак, а два. Например, при добавлении словоформы «стеной» (СТЕНА в творительном падеже) будет добавлена следующая последовательность пар знаков: «с: С», «т: Т», «е: Е», «н: Н», «о: А», «й:_».

    Все словоформы слов «стена» и «стрела» в таком автомате будут выглядеть так:



    Такой подход к записи нормальной формы обладает важным достоинством. Он позволяет работать с морфологией в двух направлениях. Можно по словоформе получить ее разбор — анализ. А можно по нормальной форме получить все ее словоформы — синтез.

    Недостатком такого подхода является то, что несмотря на то, что для пары знаков автомат является детерминированным, то для входного он уже не является таковым и надо перебирать все переходы из данного состояния. Например состояние m, на рисунке выше. В нем имеется несколько переходов по знаку словоформы «а».

    Хранение данных в переходах. Использование аннотаций


    Другой способ для хранения дополнительных данных был описан в оригинальной работе. Он предполагает изменение самих строк, которые хранятся в автомате.

    Предлагается сделующая схема. Вместо целевой строки в автомат записывается расширенная строка, которая состоит из целевой строки, символа начала данных (аннотирующего символа) и самих данных.

    Например, в этом случае морфологические характеристики могут быть записаны следующим образом: «стена|+сущ+жен+им, ...», где '|' — аннотирующий символ, а "+cущ", "+жен", "+им" — специальные символы данных.

    Этот подход используется в системе АОТ. В ней в качестве данных хранится фактически две ссылки: на морфологические характеристики и на номер правила словоизменения. В результате при анализе можно по словоформе получить как ее морфологические признаки, так и начальную форму.

    Особенностью этого подхода является то, что несколько усложняется модель автомата. Символ перехода интерпретируется по-разному в зависимости от того был он до аннотирующего символа или после.

    Другой особенностью является то, что для обход по строке несколько усложняется. Во-первых, строка присутствует в автомате, если после ее обхода мы оказываемся в состоянии, из которого есть переход по аннотирующему символу. Во-вторых, необходима процедура сбора всех аннотаций после аннотирующего символа. В третьих, необходима процедура декодирования аннотации.

    Оптимизация объема памяти


    Для оптимизации объема памяти используется два представления конечных автоматов: один для построения минимального автомата, а другой — для анализа. Разница между ними в том, что автомат для анализа не предполагает изменений и поэтому может быть более эффективно размещен в памяти.

    Автомат для анализа состоит из трех структур:
    1. таблица переходов — пары целых {символ перехода, целевое состояние}
    2. индексы начала и конца диапазона переходов состояния
    3. таблица данных финальных состояний

    Автоматы получаются достаточно компактными. Например, словарь АОТ без особых ухищрений занимает около 8Мб. Полные данные системы морфологического анализа, которые включают в себя не только анализ по словарю, но и предиктивный анализ слова умещаются в 16Мб.

    Сами алгоритмы минимизации реализованы в моем проекте на Github: github.com/kzn/fsa
    Поделиться публикацией
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

    Комментарии 40

      –8
      Ужас, бросайте это дело — вы знаете русский еще хуже меня, а я его не знаю, но догадываюсь, что:

      МЫТЬ — никак не может быть прошедшим временем(скорее будущим), не имеет ни числа ни рода(подозреваю это справедливо для всех глаголов в будущем продолженном времени, ибо он\она\они будут «делать»), про изъявительное наклонение тоже не ясно без вспомогательных слов…

      А вообще вся таблица полный бред…
        +6
        Пример не про анализ слова «мыть», а про анализ слова «мыла». «МЫТЬ» в таблице — нормальная форма.
      • НЛО прилетело и опубликовало эту надпись здесь
          0
          Спасибо.

          Кстати, под трансдюсерами разные люди понимают разные вещи. Ты, если я правильно понимаю, говоришь по weighted FST. А вот разработчики GATE трансдюсером называют обычный КА, с финальным состоянием которого ассоциированы некие действия.
          • НЛО прилетело и опубликовало эту надпись здесь
              0
              Кажется, что дело в деталях. В случае GATE используется обычная минимизация ДКА с некоторыми тонкостями для представления групп.

              Для weighted на первый взгляд нужны совершенно другие алгоритмы.

              Про эквивалентность — ну вот подход ЭТАПа — построение классического трансдюсера, но если сделать из него КА, который на конечном состоянии выдаст нормальную форму, то он будет сильно большего размера.

              И с трансдюсерами кажется отдельная задача — детерминирование по входному/выходному символу.

              Просто к чему я это все. У меня на гитхабе там рядом выдрана из GATE работа с общим КА(удаление эпсилон-переходов, НКА -> ДКА, минимизация ДКА). Но для трансдюсеров, тем более с весами, нужны другие алгоритмы.

              • НЛО прилетело и опубликовало эту надпись здесь
            +1
            Для трансдьюсера не существует способа минимизации. То есть минимизировать можно, но автомат в результате не будет гарантированно минимальным (и единственно возможным). Чтобы детерминировать трансдьюсер, нужно чтоб выполнялось свойство проективности, а это на практике редкость (на моей, по крайней мере). Но есть разные обходные пути, типа воспринимать пару символов a:b как оду метку, минимизировать как обычный акцептор.

            А чем вам OpenFST не нравится? Ребята хорошо потрудились. Правда, в погоне за универсальностью вышло тяжеловесно. Но вцелом, работает.
            • НЛО прилетело и опубликовало эту надпись здесь
                0
                Согласен. Иногда лучше вообще не минимизировать :). Вообще, там есть такая штука, как ленивая композиция. Очень эффективная, когда приходится строить композицию больших автоматов, а потом искать кратчайший путь. Но ее тяжеловато использовать — функция не вынесена в шелл-скрипты, и документации мало.
            0
            Складывается ощущение, что все описанное имеет отношение только к морфологии.

            Но ведь очевидным желанием является хранить внутри представлений слов как минимум синтаксические свойства слов (ок, на следующем этапе и т. д.) Ведь в конце концов ваш пример с «мама мыла раму» — он про синтаксис. В конечном итоге задача сведется к ответу на вопрос «мыла» — это «мыло» или «мыть». Да и ссылки на примеры систем автоматической обработки текстов — они как минимум не про чистую морфологию.

            Соответственно, у переходов в дереве состояний должны быть какие-то веса/вероятности/etc, сигнализирующие морфологические изменения в зависимости от синтаксической роли. Ну или как-то еще структура должна позволять (в будущем) хранить эту (а возможно и другие типы) информации о словах.

            Получается, что весь разговор про оптимизацию структур нужно вести в контексте возможности масштабирования и возможности «навески» дополнительных аспектов. Иначе может получиться, что оптимизированное представление, рассчитанное только на морфологическую информацию, не позволит использовать словарь для более-менее реальных прикладных задач.

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

              Обычно анализ текста выглядит примерно так: токенизация, морфологический анализ, [другие стадии анализа].

              Вот эти другие стадии анализа бывают очень разными. Следующая классическая стадия — синтаксический анализ. Но он очень ресурсоемкий как с точки зрения построения системы, так и с точки зрения ресурсов для анализа. Во многих случаях достаточно поверхностного анализа на основе списков слов — газетиров. Это фактически тот же морфологический словарь, но другого назначения. Например это — личные имена, фамилии, названия городов, улиц, железнодорожных станций, станций метро. Эти списки тоже надо как-то компактно представлять. А для более-менее приемлемого качества выделения такого рода объектов достаточно простых шаблонных правил вида: [Имя] [Фамилия] или [Фамилия] [Имя] [Отчество]. Эти правила — фактически регулярные выражения, только не над символами строки, а над словами текста. Этот подход используется, например в GATE и позволяет достаточно хорошо выделять объекты.

              Мне хотелось написать пост по одной конкретной теме. Например, есть совершенно другая тема — разрешение частеречной омонимии — POS Tagging, на котором обычно и выбирается одна из альтернативных форм слова. (Но, например, в системе ЭТАП-3 другой принцип — там омонимия разрешается одновременно с синтаксическим анализом).
                0
                Ну, то есть, я правильно понимаю, что все рассуждения про оптимизацию здесь справедливы только для частного случая морфлогического анализа и описываемый подход может оказаться неприемлем, если задача расширяется до синтаксиса?
                  0
                  Да. это морфологический, и околоморфологический анализ.
              • НЛО прилетело и опубликовало эту надпись здесь
                +1
                А в чем смысл в такой упаковке?

                Ну, 5 миллионов словоформ.
                Средняя длина русского слова в utf8 если мне не изменяет память 17 байт (могу ошибаться, давно занимался).
                Словарь константный, т.е. апдейтов/инсертов/блокировок нет.

                Получаем огромное страшное число — 85 мегабайт данных.

                Плюс perfect hash (например cmph.sourceforge.net/) — так там несколько бит на запись оверхеда всего.
                Ну плюс флаги, падежи, ссылки на нормальные формы.

                Как-то не так уж и много.

                У меня такие системы на perfect hashes — 10^8 записей и ~700 нс на извлечение записи по ключу занимали, и это еще на компах подревнее нынешних.
                Имхо как-то побыстрее префиксных деревьев.

                А если размер надо уменьшать, а не время доступа, тогда нужны succinct structures.
                Имхо префиксные деревья — не самое лучшее решение.
                  0
                  Спасибо за ссылку.

                  Но задача несколько отличается от perfect hash. Надо по строке получать нормальную форму и морфологические характеристики. Это тоже занимает достаточно много места.

                  Я вот сейчас поставил cmph, прогнал просто список словоформ. Получил, что данные для хеша занимают 21Мб. Время построения — сходное с построением минимального КА. Минимальный КА занимает меньше даже без особой экономии памяти.

                  Преимущество автомата как раз в том, что его можно менять. В ЭТАПе как раз так и сделано. Есть словарь, который правят лингвисты, он также хранится в виде КА. И КА изменяется на лету без перестроения всего автомата.

                  Опять же, не было задачи ужать все до минимальных размеров. При желании автомат можно упаковать очень сильно. Например, если переходы изпользовать дельта и varint кодирование для меток переходов. В общем все, что описано в www.aclweb.org/anthology/W/W09/W09-1505.pdf

                    0
                    Да, perfect hash константный, за счет чего и скорость запросов обеспечивается.
                    Я делал обновления оффлайном, с переключением на лету, у меня задача была — высоконагруженный веб-сервис.
                    Тем более, что на объемах >10^6 изменения очень невелики, иногда за месяц обновлений не набиралось.
                    Время построения у меня было порядка 2 минут, объем — там смотреть надо, у них от метода хеширования зависит, minimal ordered perfect hash добавляет 32 или 64 бита к каждой записи. Если же он не упорядоченный, то там реально очень небольшие размеры, плюс они хранят их в компрессированном виде.

                    Морфологическая информация и нормальная форма (точнее то, что у меня было их аналогом) хранилась в массиве, смещение в котором и возвращал хеш (как ID).

                    Для задачи где много вставок или изменений конечно такой метод неприменим.

                    А вот там, где база практически не меняется, размеры большие (billions records как пишут авторы) и скорость анализа текста критична — там что доктор прописал.
                    Я быстрее пока не встречал (из того что сам лично щупал, понятно).
                    Сейчас вот WordNet думаю туда перегнать.

                    В общем рекомендую, хорошая либа, хотя со своими тараканами.
                    Например в случае дубликатов она тупо крешится при построении хеша.
                    Ну и там еще по мелочи — поведение не всегда очевидное.
                    • НЛО прилетело и опубликовало эту надпись здесь
                        0
                        Ага, мне тоже так говорили, что он ломается на определенных размерах.
                        И приводили примеры — реально ломающиеся, раз так пять показывали и тыкали мордой.
                        И я во всех пяти случаях смотрел данные и находил дубликаты, он же гарантированно ломается при построении, если данные дублируется. Это у него фича такая.
                        :-)

                        Ну и тормознутость perfect hash по сравнению с обычным — это как раз странно (конечно если это не gperf).
                        На запросах cmph быстрее, я еще делал анализ когда он был 1-й версии, сравнивал его даже с такой прикольной экзотикой как uthash — на макросах который.
                        По запросам cmph был лидером — там только надо правильный тип выбрать (у меня BDZ по дефолту стоял), у разных типов скорость доступа разная.

                        На построении там да, разные скорости бывают, но для таких баз данные перестраиваются крайне редко.
                        Одно дело на десктопе у лингвистов, другое дело — на ядре сервиса.

                        Правда на 32 битах ни разу не гонял, хз, может там действительно есть проблемы, врать не буду.
                        • НЛО прилетело и опубликовало эту надпись здесь
                            0
                            Сейчас проверил, на второй версии вроде не падает по дубликатам, возвращает ошибку.
                            В первой версии крешился, что было неудобно и заставляло заказчика нервничать. :-)

                            У них в доке было, что при некоторых seed создание хеша может быть неудачным, но вероятность такого события тем меньше, чем больше записей.

                            Why do I always get the error «Unable to create minimum perfect hashing function»?
                            — The algorithms do not guarantee that a minimal perfect hash function can be created. In practice, it will always work if your input is big enough (>100 keys). The error is probably because you have duplicated keys in the input. You must guarantee that the keys are unique in the input.


                            Сам ни разу не попадал чтобы падало без дубликатов, но и так чтобы меньше 10^5 никогда не строил — даже на тестах, но и там не падало. Поэтому и удивился, что на миллионах упало.

                            У меня было так — словарь слов ~20М, короткие слова 3-20 символов, но utf8, по байтам не помню статистику, но большинство символов ASCII.
                            Дополнительный словарь — пары индексов (т.е. 4+4=8 байт) — ~80М.
                            И был словарь пар слов вспомогательный (редко используемый), где-то 120М, там длинные комбинации, потом убрал его, но основные замеры на нем делал.

                            Меня память не лимитировала никак, серваки начинались от 32Г, а вот скорость была крайне критична, поэтому я тупо хранил строки в массиве не заморачиваясь, быстрее индексного доступа все равно ничего не бывает.

                            Предобработка у CMPH конечно медленная, тут даже не спорю, это тот еще тормоз.

                            По скорости доступа там на самом деле получается вот что.
                            Это хеш возвращает номер от 0 до N-1 для любой строки, даже если ее в хеше нет.
                            Поэтому потом надо еще делать прямое сравнение, что тоже какое-то время забирает, сама либа этого не делает, она сильно уж низкоуровневая.

                            Это в принципе похоже на то, что происходит в обычном хеше, но в обычном хеше в случае коллизии надо делать несколько таких сравнений, а здесь только одно единственное и гарантировано единственное. С другой стороны хеш-функция в обычном хеше сильно проще будет и в этой точке как раз может быть сравнение не в пользу cmph.

                            Хе, я даже сначала (до замеров скорости) Bloom Filter соорудил для предварительной фильтрации — однако оказалось что никакого реального профита он не дает, быстрее получить индекс и сравнить строку напрямую.
                            Кроме того по статистике запросов увидел, что большинство запросов были в хеше, так что и надобность отпала даже концептуально.

                            В принципе можно оттюнить и проверить с каким-нибудь обычным hash_map, тоже тюнированным.
                            Я еще с первой версией все измерения делал, вторую уже давно механически использую в коде без анализа.
                            На продакшене несколько лет работает, не падает, нареканий нет.

                            PS
                            Я не лингвист, это халтурка была, но такие халтурки возникают достаточно регулярно.
                            • НЛО прилетело и опубликовало эту надпись здесь
                                0
                                Достаточно интересно будет посмотреть на результаты, тем более что я например с Boost не сравнивал, на том заказе Boost был не в фаворе, потому я время тогда сэкономил.

                                Я вот думаю скорость доступа в зависимости от размера хеша как-нибудь посчитать, задержка там растет сублинейно, но заметно.
                                Ну и для каждого типа хеша задержка очень разная.

                                Я нашел старую табличку по скорости именно cmph, осталась в старых доках.
                                Процессор правда неизвестен и по другим хешам данных нет.
                                Похоже на домашней машине гонял, но на которой — уже не вспомнить.

                                10М 40-байтовых рандомных ключей, т.е. ключи достаточно длинные, на коротких понятно может быть сильно другая картина.
                                Измерялось время 1М чтений и размер хеша (без самих строк).

                                Вот что получилось

                                BDZ
                                размер 3 459 422 байт
                                время 809 мс

                                BMZ
                                размер 46 000 052 байт
                                время 656 мс

                                CHM (ordered)
                                размер 83 600 052 байт
                                время 727 мс

                                CHD
                                размер 5 293 580 байт
                                время 1288 мс

                                Все остальные настройки были по дефолту.
                                Ну и это первая версия cmph была, может даже еще 0.9.

                                Но это время вместе со сравнением строки, это не только вычисление самой функции.
                                • НЛО прилетело и опубликовало эту надпись здесь
                      0
                      Если правильно понял статью и комментарий, то штука, похожая на «дельта кодирование переходов», есть в реализации DAFSA code.google.com/p/dawgdic/. Конкретно в dawgdic есть ограничение на общее количество переходов (из-за 32битных чисел везде), так что гугл-н-граммы туда засунуть не получится. Но для морфологии работает отлично.
                        0
                        Скорее всего, судя по внушительному списку литературы там.

                        Но странно, что там реализован только алгоритм для отсортированных строк. В основной статье как раз два алгоритма: для отсоритрованных и нет.

                        Я реализовывал алгоритм, который работает без предварительной сортировки входных данных.
                          0
                          Похоже, сортировка требуется как раз из-за способа кодирования автомата: он хранится одним куском памяти, без указателей («double array»), и поэтому удаление оттуда требует перемещения большого количества данных. Видимо, с упорядоченными входными данными можно инкрементально строить автомат без необходимости удалять оттуда что-либо — или хотя бы локализовать изменения, сообразить сейчас не могу.
                      +2
                      Большинство систем морфологии создавались в бородатые времена, когда память имела больше значения. При этом скорость морфологического анализа для многих реальных задач узким местом не является: особого смысла во всех этих миллионах разборов/сек нет, когда большинство алгоритмов синтаксического анализа — O(N^3) от длины предложения. Мне кажется, из-за этого такая любовь к префиксным деревьям.

                      Насчет размера: насколько знаю, способа закодировать DAFSA (иногда aka DAWG) как «succinct data structure» пока не придумали (с сохранением хотя бы асимптотики всех операций), а для задач морфологии получается, что DAFSA занимает меньше памяти, чем всяческие succinct trie, так что уменьшить размер не получается.

                      Ну и еще в деревьях/DAFSA можно разные операции делать хитрые, в духе «пройтись по дереву, считая переходы е и ё равноценными» или «найти все возможные разборы слова», или «найти все возможные разборы слова, оканчивающегося на данную строку», они очень просто там реализуются. В случае с хэшем для каждого слова нужно ведь списки возможных разборов хранить, их ведь несколько?

                      Использование хэшей немного смещает баланс «скорость <-> память» в сторону скорости (особенно если не нужны «хитрые» операции). Получается выигрыш раз в 10 по памяти и проигрыш раза в 2-4 по скорости. Но скорости и так хватает за глаза (у меня выходило в среднем 1500ns для получения всех разборов слова из DAFSA, с учетом обертки на Python), а реализации и там, и там достаточно простые, особенно если готовые библиотеки использовать. Видимо, поэтому DAFSA используют чаще.
                        0
                        В принципе логично, DAFSA достаточно эффективен и универсален, а perfect hash — это решение одной задачи.

                        Я просто привык все решать по UNIX way — для поиска одна структура, для допустим экстракции всех n-грамм — другая…
                        Это на самом деле не всегда хорошо.

                        В данном случае возможно гибкость более практична, в реальных текстах смешивание е/ё — не самая малая из проблем.
                          0
                          Кстати, скорость важна для индексирования. Но в этом случае нужен не полный анализ, а лемматизация.
                          • НЛО прилетело и опубликовало эту надпись здесь
                          • НЛО прилетело и опубликовало эту надпись здесь
                            0
                            Для меня лично смысл в том, что упакованный словарь форм дает приятный такой баланс между размером данных и скоростью работы.

                            Плюс автомат с суффиксами ловко угадывает леммы для неизвестных слов, с хешами тоже можно, но реализация прикидочно помуторнее.
                            +3
                            Вспомнилась байка про компьютерный анализ текстов Михаила Щербакова. Программа выдала, что самые частотные глаголы у Михаила Константиновича — «мыть» и «какать». Т.к. автор программы не смог припомнить ни одной песни, в которой бы эти глаголы встречались, он провёл тщательный анализ. Выяснилось, что к этим глаголам программа привела словоформы «мой», «моя» и «какая».
                              0
                              туда же: «при» -> «переть»; «меня», «для» -> «длить»
                              0
                              А никто случайно не задался целью собрать вместе хотя бы информацию о разработчиках и п.о? тот же морфоанализ, свободные словари… Инфа есть, тот же АОТ, словари синонимов, но всё очень разрознено.
                                +1
                                Это все очень сложно. Вообще есть такой проект — nlpub.ru ведет его eveel. Но вот использовать все вместе составляет довольно большие технические трудности. Например, есть открытая морфология АОТ, с другой стороны — есть открытая часть НКРЯ (национального корпуса русского языка) с морфологической разметкой. Казалось бы, взять — и фактически готовый POS-теггер. Но в АОТ приняты одни соглашения, в НКРЯ — другие, в СинТагРусе (корпус с синтаксической разметкой) — третьи. Их частично можно преобразовывать между собой, но во многом требуется преобразование руками.

                                С другой стороны — многие разработки закрыты, причем как коммерческие, так и академические. И разработчики ими делятся не очень охотно. Это тоже понятно — разработка лингвистических ресурсов трудоемко.

                                  0
                                  Ну так присоединяйтесь к NLPub, будем рады видеть. У нас всё это есть и мы работаем на CC BY-SA :)
                                  +1
                                  Пару лет назад реализовывали Дацюка для неупорядоченной последовательности входящих строк. Есть статья, в ней сравнение mafsa с популярными встраиваемыми реализациями БД sqlite и BerkeleyDB, и с std::map, а также о том, как по-разному можно использовать mafsa даже не в формате трансдюсера. Вы здорово объяснили алгоритм, буду теперь молодым коллегам давать ссылку.

                                  Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                  Самое читаемое