Разве есть такое слово "линковщик"? Компиляция и компилятор — это слова русского языка, а вот препроцессор с линковщиком — нет. Кстати, почему линковщиком, а не линкование? Или ещё хорошее слово: "препроцессировка", здорово, правда? Не знаю, есть английский глагол to link, по нашему связывать. Назначение программы linker состоит в связывании различных модулей компиляции в модуль исполнения, где тут "линковка" совершенно непонятно. Предлагаю ввести в обиход слова: мапировка, хэшировка, лукапирование и т.п.
Вопрос к уважаемому автору: почему вместо устоявшегося в литературе термина «связывание» Вы используется англицизм «линковка»? Слова такого в русском языке вроде не наблюдается, и звучит как «приспособа», чем-то из токарно-столярного дела отдает.
Не понятно, почему низкое качество получится. Если не нужно выделять классы слов, т.е. приводить их в какую-то нормальную форму, то все опечатки и форму таки или иначе будут присутствовать в словаре, полученном на обучающей выборке. Для описанной в статье задачи никто не гарантирует, что приведение к нормальной форме повысит качество до 90%. Ну а для Вашей задачи вообще не понятно, к чем приведет такой улучшение. Качество для таких задач обычно улучшают расширением контекста. Самое простое решение — использовать словный n-граммы вместо слов (униграмм). Еще радикальнее — прогнать все тексты из обучающей выборки через word2vec и использовать вектора чисел, полученные для слов этим алгоритмом. Эти вектора учитывают синтаксическую синонимию (употребление слов в одном контексте), тогда к нормальной форме вообще не нужно ничего преобразовывать.
В чем проблема, почему просто не использовать UNICODE внутри, а снаружи UTF-8? Если классификация на словах, то слова — это последовательности символов, разделенные сепаратором (есть такой класс символов в UNICODE). Будут английские, русский, украинский (по желанию и китайские) слова, выделенные из текста как признаки. В чем здесь трудность?
UNICODE это не только преобразование из utf-8 в utf-32 и обратно, там главное — классификация символов. В библиотеке Strutext https://github.com/merfill/strutext реализован UTF-8 итератор по байтовому потоку, а также в symbols.h определены классы символов и функция определения класса по его коду. Код итератора — это адаптация библитеки разбора utf-8 от unicode.org, там сделано хорошо и быстро. Классы символов лежат в файле UnicdeData.txt, это родная база классов символов от unicode.org, которая при сборке проекта парсится в сишные структуры.
Ну да, ясное дело, что трай — это автомат. Я спрашиваю, почему просто не ходить по траю с операциями редактирования, как я описал? Зачем заводить какие-то дополнительные структуры?
Интересно, а почему вообще нужен специальный автомат? Я для правки опечаток в поисковых запросах использовал обычный трай словоформ. Словарь для трая можно использовать любой, например, все тот же словарь Зализняка из АОТ. Для нечеткого поиска в словаре используем алгоритм, схожий с обходом недетерминированного автомата. Расширяем состояние двумя атрибутами: позицией в исходной строке и штрафом за операции редактирования. В каждый момент времени обхода автомата имеется множество таких состояний. Переход для каждого состояния осуществляется соответственно операциям редактирования: для удаления символа меняем только позицию в строке в состоянии и увеличиваем штраф, для замены делаем переход по всем символам, у которых есть переходы из данного состояния, увеличиваем позицию в строке и штраф, если символ перехода не совпадает с символом в строке. Вставка похожа на замену, только позиция в строке не увеличивается.
Например, пусть с трае у нас две словоформы: мама и папа и на вход дана словоформа «ама». В начале имеет состояние { 0, 0, 0 }, с начальным номером, нулевой позицией в строке и нулевым штрафом. Переходы из начального состояния: { 0, 0, 1 } (удаление а), { 1, 0, 1 } (вставка м), { 2, 0, 1 } (вставка п), { 1, 1, 1 } (замена а на м) и { 2, 1, 1 } (замена а на п). Для каждого из этих состояний также генерируются переходы. Если мы допускаем не более одной операции редактирования, то переходы из всех состояний, кроме { 1, 0, 1 } и { 2, 0, 1 }, увеличат штрафы, а для этих состояний будет произведен переход по символу «а»: { 1, 0, 1 } --> { 3, 1, 1 } и { 2, 0, 1 } --> { 4, 1, 1 }. Это без штрафа, со штрафом также будут сгенерированы переходы с редактированием, но они не будут добавлены по порогу. В результате мы дойдем с этими двумя состояниями до символа «м». Там перехода для пути по «папа» не будет, будет произведена замена «м» на «п» со штрафом и дальше не пойдем по порогу штрафа. А вот по пути «мама» дойдем до допускающего состояния и распознаем это слово с одной операцией редактирования.
Для поисковых запросов, который состоят из множества слов, можно также делать переходы по пробелам (между словами) из допускающих состояний и переходы со вставкой пробела из допускающего состояния (когда пробел между словами в запросе пропущен).
В литературе я этого способа вычисления дистанции Левенштейна по словарю не нашел. Может, Вы подскажете, что-то такое встречалось?
Как-то задача нечетко сформулирована. Насколько я понял, необходимо найти группы товаров, описания которых синтаксически схожи. При этом, хочется избавиться от шума, т.е. от ошибок в описаниях. Это, по большому счету, две разные задачи, которые однако в обработке текстов можно свести к одной задаче — выделению признаков.
Задача 1: для двух описаний определить метрику (ну наверное, метрику, раз кластеризацию хочется делать в евклидовом пространстве, имея ввиду задачу 2) схожести так, чтобы игнорировать ошибки написания. Такая задача решается в алгоритмах поиска исправления поискового запроса с опечатками. Один из наиболее распространенных методов — выделить из текстов символьные n-граммы, т.е. представить каждый текст как множество n-грамм (может быть, снабженных дополнительным атрибутом, частотой это n-граммы в тексте) и сравнить два множества. Если множества почти одни и те же, то и исходные тексты похожи. Вы, насколько я понимаю, примерно это и использовали, выделяемые из текстов шинглы и есть эти самые n-граммы. Тут можно еще на основе статистики встречаемости шинглов (n-грамм) во всем корпусе определить их важность (tf/idf или какие-то другие критерии). Важность можно умножать на частоту шингла в тексте описания.
Задача 2: найти на основе определенной метрики множества схожих описаний товаров. Тексты описаний короткие, поэтому задача кластеризации должна решаться легче, в том смысле, что похожие описания должны образовывать ярко выраженные кластера. Если решать задачу в лоб, то необходимо сравнить каждое описание с каждым другим описанием, т.е. имя N описаний необходимо сделать N^2 сравнений. Это, понятное дело, очень долго при большом N. Я обычно использую инвертированный поисковый индекс для сравнения двух текстов. Все тексты индексирую в таком индексе, в качестве элементов для индексирования выступают шинглы (слова или последовательности слов или символов). Для текста, который надо сравнить со всеми остальными, выделяю шинглы, ищу тексты, в которых эти шинглы встречаются и, таким образом, нахожу множества шинглов для каждого текста (пересечение). Те тексты, пересечение которых достаточно большое, выбираю для подсчета метрики схожести. В результате, вместо N^2 получаю N log N, что для больших N быстро.
На практике, полученное таким образом множество схожих текстов еще надо проредить. Для этого можно придумать много алгоритмов, но обычно достаточно достаточно простых вычислений на основе статистики корпуса индексированных текстов. Я обычно использую библиотеку xapian для организации индексирования, она написана на C++, но есть интерфейсы на python. Подобный подход реализовал, например, для онлайн кластеризации текстов из соцмедиа. Там идет поток документов порядка 10-50 в секунду, надо образовывать кластера схожих документов. Алгоритмы, конечно, посложнее, чем я описал, но принцип тот же. Для кластеризации используется один мастер-сервер, который ищет похожие документов для переданного в потоке, а потом передает документ на индексирование в slave-сервера, которые представляют собой такие вот поисковые индексы. Один мастер и 5 слейвов вполне себе справляются с такой нагрузкой.
Английский словарь от АОТ тоже реализован в библиотеке. Немецкий вроде бы тоже был (не помню точно, у них или в другом месте). Кроме, собственно, словаря, необходимо еще реализовать модель синтаксических категорий. Скажем, для украинского кроме словаря основ и наборов склонений надо еще разработать модель синтаксических категорий (части речи, падежи, число, время и т.п.) и реализовать ее в C++. Можно и без категорий, но это уже будет обычный стеммер, т.е. будет возвращать основу без указания лексических атрибутов. В любом случае, здесь все зависит от задачи, есть много задач, для которых учет словоизменения не нужен, для других задач необходим только стеммер. Синтаксические категории используются в синтаксическом анализе, так что обычно необходимы для более глубокого анализа текста.
Относительно сленга и другой подобной лексики. Для реализации морфологии есть два принципиально различных подхода: реализация на основе сделанного вручную словаря (типа словаря Зализняка и его производных, в том числе и АОТ) и реализация на основе статистики. Словарная морфология используется, например, в Яндексе. Вероятностные морфологические модели, насколько я слышал, используются в Google. Соответственно, для работы со сленгом необходимо выбрать один из этих подходов. Первый подход это расширение словаря (того же АОТ) вручную, добавление новых основе и парадигм склонения. Второй подход, построение моделей на основе размеченных текстов, таких текстов должно быть достаточно для построения модели.
Пополнение словаря — задача возникающая довольно часто. Нужен специальный инструмент (GUI) для пополнения, чтобы давал возможность добавить корень, выбрать парадигму склонения или добавить свою. Это инструмент для лингвистов — «рабочее место лингвиста». Хотя, конечно, если такой новой лексики относительно немного, то можно использовать и непосредственно разработчиков для пополнения словаря. Насколько я помню, в Яндексе именно так и делают.
Конечно, если словарь новый и относительно небольшой, то просится в использование построение вероятностной морфологической модели. Я, честно говоря, специальных инструментов прямо для построения такой модели не знаю. Может кто-то подскажет прямо здесь?
Относительно портирования на другой язык, это зависит от того, какой язык Вам необходим. На сайте АОТ Вы можете найти ссылки на реализации морфологии на Java и python. Наверное есть и реализации на каких-то других языках. Библиотека Strutext была сделана специально для языка C++ и основана на специфических именно для этого языка подходах. Например, потоковая обработка текста с помощью итераторов — шаблонных классов, совместимых с STL итераторами. Возможность классификации символов в UNICODE по одному символу (в ICU для этого надо использовать сишные макросы, а модель классов — прямая калька от Java модели со всеми присущими недостатками). Легкие поточные перекодировщики для UTF-8 и однобайтовых кодировок. Ну и более сложные итераторы, итератор по словам, итератор по последовательностям слов, быстрый поиск наборов слов в тексте и т.п.
Тон какой-то выбран излишне агрессивный, что-то личное? По теме, я не специалист по UNICODE, понятное дело, но вроде UTF-8 кодировку от UTF-16 отличить могу. Ниже я приводил код из программы, которая перекодирует UTF-8 последовательности в UTF-32 коды. Из кода видно, что в UTF-8 может использоваться до шести байтов включительно (даже не четыре, бывает и шесть), чтобы закодировать символ UNICODE. Именно для этой цели я и приводил код. Рассчитывал, что человек, который понимает UNICODE, видел и их код на C для перекодирования UTF-8 в UTF-32. Ну, наверное, просто опыта с C++ нет, потому и весь код мимо.
В кодировке UTF-16 для некоторых символов, коды которых не вмещаются в 2^16, используется четыре байта. Для эффективного кодирования классификатора символов на UTF-16 надо сделать нечто более сложное, чем просто обращение к ячейке памяти по коду (как это делается в UTF-32). Наверное, надо сделать сравнение на определенное число, если код больше этого числа, перейти на вектор дополнительных кодов для данного кода и найти соответствующий класс. Это все займет время и будет не так эффективно.
Вообще, в массиве классов хранятся не коды символов, а флаги классов для каждого символа, которые в любом случае занимают 4 байта и, собственно, к коду символа не имеют никакого отношения. А дискуссию относительно преимуществ и недостатков использования UTF-32 для классификации можно прочитать на сайте UNICODE, там приведены соответствующие соображения.
Хотелось такие коды представлять естественным образом. Экономить на памяти 12 Мб против 24 Мб в наше время полагаю анахронизмом. Кому это надо, если chromium-browse у меня сейчас жрет 150 Мб, а thunderbird — 250?
Ну, предполагалось, что для более полного представления юникода. Всякие там сурогаты можно класть. Хотя, на самом деле, хотел полной поддержки работы UTF-8 итератора, код которого (в виде синшных функций) я взялс unicode.org. Там есть такой код:
// Go to loop of UTF-8 sequence reading.
uint32_t decoded_symbol = 0;
switch (extra_bytes_to_read) {
case 5:
symbol_.chain_[0] = *iter_;
decoded_symbol += static_cast<uint8_t>(*iter_);
decoded_symbol <<= 6;
if (not Next()) {
return;
}
case 4:
symbol_.chain_[extra_bytes_to_read-4] = *iter_;
decoded_symbol += static_cast<uint8_t>(*iter_);
decoded_symbol <<= 6;
if (not Next()) {
return;
}
case 3:
symbol_.chain_[extra_bytes_to_read-3] = *iter_;
decoded_symbol += static_cast<uint8_t>(*iter_);
decoded_symbol <<= 6;
if (not Next()) {
return;
}
case 2:
symbol_.chain_[extra_bytes_to_read-2] = *iter_;
decoded_symbol += static_cast<uint8_t>(*iter_);
decoded_symbol <<= 6;
if (not Next()) {
return;
}
case 1:
symbol_.chain_[extra_bytes_to_read-1] = *iter_;
decoded_symbol += static_cast<uint8_t>(*iter_);
decoded_symbol <<= 6;
if (not Next()) {
return;
}
case 0:
symbol_.chain_[extra_bytes_to_read] = *iter_;
decoded_symbol += static_cast<uint8_t>(*iter_);
}
// Magic numbers to process decoding.
static const uint32_t OFFSETS_FROM_UTF8[6] = {
0x00000000UL, 0x00003080UL, 0x000E2080UL, 0x03C82080UL, 0xFA082080UL, 0x82082080UL
};
decoded_symbol -= OFFSETS_FROM_UTF8[extra_bytes_to_read];
symbol_.len_ = extra_bytes_to_read + 1;
// Is the sequence legal?
if (IsLegalUtf8((const uint8_t*)symbol_.chain_, symbol_.len_)) {
// Increase symbol counter only, if correct symbol extracted.
symbol_.utf32_ = decoded_symbol;
++sym_pos_;
}
Разве есть такое слово "линковщик"? Компиляция и компилятор — это слова русского языка, а вот препроцессор с линковщиком — нет. Кстати, почему линковщиком, а не линкование? Или ещё хорошее слово: "препроцессировка", здорово, правда? Не знаю, есть английский глагол to link, по нашему связывать. Назначение программы linker состоит в связывании различных модулей компиляции в модуль исполнения, где тут "линковка" совершенно непонятно. Предлагаю ввести в обиход слова: мапировка, хэшировка, лукапирование и т.п.
Например, пусть с трае у нас две словоформы: мама и папа и на вход дана словоформа «ама». В начале имеет состояние { 0, 0, 0 }, с начальным номером, нулевой позицией в строке и нулевым штрафом. Переходы из начального состояния: { 0, 0, 1 } (удаление а), { 1, 0, 1 } (вставка м), { 2, 0, 1 } (вставка п), { 1, 1, 1 } (замена а на м) и { 2, 1, 1 } (замена а на п). Для каждого из этих состояний также генерируются переходы. Если мы допускаем не более одной операции редактирования, то переходы из всех состояний, кроме { 1, 0, 1 } и { 2, 0, 1 }, увеличат штрафы, а для этих состояний будет произведен переход по символу «а»: { 1, 0, 1 } --> { 3, 1, 1 } и { 2, 0, 1 } --> { 4, 1, 1 }. Это без штрафа, со штрафом также будут сгенерированы переходы с редактированием, но они не будут добавлены по порогу. В результате мы дойдем с этими двумя состояниями до символа «м». Там перехода для пути по «папа» не будет, будет произведена замена «м» на «п» со штрафом и дальше не пойдем по порогу штрафа. А вот по пути «мама» дойдем до допускающего состояния и распознаем это слово с одной операцией редактирования.
Для поисковых запросов, который состоят из множества слов, можно также делать переходы по пробелам (между словами) из допускающих состояний и переходы со вставкой пробела из допускающего состояния (когда пробел между словами в запросе пропущен).
В литературе я этого способа вычисления дистанции Левенштейна по словарю не нашел. Может, Вы подскажете, что-то такое встречалось?
Задача 1: для двух описаний определить метрику (ну наверное, метрику, раз кластеризацию хочется делать в евклидовом пространстве, имея ввиду задачу 2) схожести так, чтобы игнорировать ошибки написания. Такая задача решается в алгоритмах поиска исправления поискового запроса с опечатками. Один из наиболее распространенных методов — выделить из текстов символьные n-граммы, т.е. представить каждый текст как множество n-грамм (может быть, снабженных дополнительным атрибутом, частотой это n-граммы в тексте) и сравнить два множества. Если множества почти одни и те же, то и исходные тексты похожи. Вы, насколько я понимаю, примерно это и использовали, выделяемые из текстов шинглы и есть эти самые n-граммы. Тут можно еще на основе статистики встречаемости шинглов (n-грамм) во всем корпусе определить их важность (tf/idf или какие-то другие критерии). Важность можно умножать на частоту шингла в тексте описания.
Задача 2: найти на основе определенной метрики множества схожих описаний товаров. Тексты описаний короткие, поэтому задача кластеризации должна решаться легче, в том смысле, что похожие описания должны образовывать ярко выраженные кластера. Если решать задачу в лоб, то необходимо сравнить каждое описание с каждым другим описанием, т.е. имя N описаний необходимо сделать N^2 сравнений. Это, понятное дело, очень долго при большом N. Я обычно использую инвертированный поисковый индекс для сравнения двух текстов. Все тексты индексирую в таком индексе, в качестве элементов для индексирования выступают шинглы (слова или последовательности слов или символов). Для текста, который надо сравнить со всеми остальными, выделяю шинглы, ищу тексты, в которых эти шинглы встречаются и, таким образом, нахожу множества шинглов для каждого текста (пересечение). Те тексты, пересечение которых достаточно большое, выбираю для подсчета метрики схожести. В результате, вместо N^2 получаю N log N, что для больших N быстро.
На практике, полученное таким образом множество схожих текстов еще надо проредить. Для этого можно придумать много алгоритмов, но обычно достаточно достаточно простых вычислений на основе статистики корпуса индексированных текстов. Я обычно использую библиотеку xapian для организации индексирования, она написана на C++, но есть интерфейсы на python. Подобный подход реализовал, например, для онлайн кластеризации текстов из соцмедиа. Там идет поток документов порядка 10-50 в секунду, надо образовывать кластера схожих документов. Алгоритмы, конечно, посложнее, чем я описал, но принцип тот же. Для кластеризации используется один мастер-сервер, который ищет похожие документов для переданного в потоке, а потом передает документ на индексирование в slave-сервера, которые представляют собой такие вот поисковые индексы. Один мастер и 5 слейвов вполне себе справляются с такой нагрузкой.
Относительно сленга и другой подобной лексики. Для реализации морфологии есть два принципиально различных подхода: реализация на основе сделанного вручную словаря (типа словаря Зализняка и его производных, в том числе и АОТ) и реализация на основе статистики. Словарная морфология используется, например, в Яндексе. Вероятностные морфологические модели, насколько я слышал, используются в Google. Соответственно, для работы со сленгом необходимо выбрать один из этих подходов. Первый подход это расширение словаря (того же АОТ) вручную, добавление новых основе и парадигм склонения. Второй подход, построение моделей на основе размеченных текстов, таких текстов должно быть достаточно для построения модели.
Пополнение словаря — задача возникающая довольно часто. Нужен специальный инструмент (GUI) для пополнения, чтобы давал возможность добавить корень, выбрать парадигму склонения или добавить свою. Это инструмент для лингвистов — «рабочее место лингвиста». Хотя, конечно, если такой новой лексики относительно немного, то можно использовать и непосредственно разработчиков для пополнения словаря. Насколько я помню, в Яндексе именно так и делают.
Конечно, если словарь новый и относительно небольшой, то просится в использование построение вероятностной морфологической модели. Я, честно говоря, специальных инструментов прямо для построения такой модели не знаю. Может кто-то подскажет прямо здесь?
Относительно портирования на другой язык, это зависит от того, какой язык Вам необходим. На сайте АОТ Вы можете найти ссылки на реализации морфологии на Java и python. Наверное есть и реализации на каких-то других языках. Библиотека Strutext была сделана специально для языка C++ и основана на специфических именно для этого языка подходах. Например, потоковая обработка текста с помощью итераторов — шаблонных классов, совместимых с STL итераторами. Возможность классификации символов в UNICODE по одному символу (в ICU для этого надо использовать сишные макросы, а модель классов — прямая калька от Java модели со всеми присущими недостатками). Легкие поточные перекодировщики для UTF-8 и однобайтовых кодировок. Ну и более сложные итераторы, итератор по словам, итератор по последовательностям слов, быстрый поиск наборов слов в тексте и т.п.
В кодировке UTF-16 для некоторых символов, коды которых не вмещаются в 2^16, используется четыре байта. Для эффективного кодирования классификатора символов на UTF-16 надо сделать нечто более сложное, чем просто обращение к ячейке памяти по коду (как это делается в UTF-32). Наверное, надо сделать сравнение на определенное число, если код больше этого числа, перейти на вектор дополнительных кодов для данного кода и найти соответствующий класс. Это все займет время и будет не так эффективно.
Вообще, в массиве классов хранятся не коды символов, а флаги классов для каждого символа, которые в любом случае занимают 4 байта и, собственно, к коду символа не имеют никакого отношения. А дискуссию относительно преимуществ и недостатков использования UTF-32 для классификации можно прочитать на сайте UNICODE, там приведены соответствующие соображения.
Старший код это
Хотелось такие коды представлять естественным образом. Экономить на памяти 12 Мб против 24 Мб в наше время полагаю анахронизмом. Кому это надо, если chromium-browse у меня сейчас жрет 150 Мб, а thunderbird — 250?