tgoop.com/reverse13/704
Last Update:
Вы наверно знаете, что такое конечные автоматы.
Но возможно, как и я до недавнего времени, не слышали об FST.
По сути это тоже конечный автомат, где переход помимо входной метки содержит выходную (она может быть из другого алфавита), плюс можно добавить вес (которому нужно быть элементом полукольца только если вам нужны все свойства и алгоритмы).
Почему у этого есть отдельное название? Вероятно потому что для fst придумали алгоритмы минимизации, конкатенации и тд, которые сохраняли бы получившуюся структуру.
В целом теория неплохо описана в статье.
Еще эта структура данных примечательна тем, что имеет полезные применения:
- Используется для хранения словаря термов (и не только) в lucene и других поисковых движках. Кстати в качестве полукольца веса может быть и строка
- В распознавании речи в kaldi, статья довольно подробно описывает зачем, только учитывайте, что за исключением части раздела 2 и раздела 4 это по большей части повторение первой статьи.
Как я думаю следствием этого является наличие вменяемых имплементаций.
Например гугловая библиотека C++ OpenFST, ее используют kaldi и например мы в ArangoDB.
Поэтому если вам нужна библиотека обычных конечных автоматов (к сожалению я не встречал нормальных, в основном про fsm в компайл тайме для функций) можно использовать FST.
Например я недавно использовал для поиска наибольшего общего префикса.
Но зачем вообще в ArangoDB OpenFST? Мы используем ее в https://github.com/iresearch-toolkit/iresearch (аналог lucene), правда с некоторыми патчами.
Поставьте нам в iresearch звездочку кстати!
К сожалению OpenFST не без недостатков, что неудивительно учитывая что либа была написана еще в 2000-ых:
- bazel/make как система сборки, это типичный недостаток гугловых/старых либ, но это не большая проблема, можно написать свой простенький cmake для нужного вам (есть в iresearch)
2. То что это все живет не на условном github/gitlab/etc, хз принимают ли они патчи например, ну и в целом мне кажется это сказывается на активности разработки.
3. В либе много довольно странного API, который стоило бы задеприкейтить.
В целом ощущение что оно почти не развивается
Если же говорить про другие библиотеки fst, я видел несколько любопытных на rust:
- Попытка переписать openfst
- Реализация fst на rust, которая используется в tantivy
Собственно имплементация в lucene
Вроде бы еще что-то есть на java но я не интересовался
Еще постараюсь до нг написать про fault-injection немного и геометрию
BY Loser story
Share with your friend now:
tgoop.com/reverse13/704