Лекция
Привет, Вы узнаете о том , что такое Библиотека FST, Разберем основные их виды и особенности использования. Еще будет много подробных примеров и описаний. Для того чтобы лучше понимать что такое Библиотека FST , настоятельно рекомендую прочитать все из категории Индексирование большого набора ключей с помощью конечных автоматов.
fst Клеть (слово Руста для «единиц компиляции») я построил написано в Русте, быстро и память в сознании. Он предоставляет две удобные абстракции вокруг упорядоченных наборов и упорядоченных карт, а также обеспечивает прямой доступ к базовому преобразователю конечного состояния. Загрузка наборов и карт с использованием карт памяти - это первоклассная функция, которая позволяет запрашивать наборы или карты без предварительной загрузки всей структуры данных в память.
Возможности упорядоченных множеств и отображений зеркала , что из BTreeSet и BTreeMap находятся в стандартной библиотеке Руста. Ключевое отличие состоит в том, что наборы и отображения fstнеизменяемы, ключи фиксируются в байтовых последовательностях, а значения в случае карт всегда представляют собой 64-битные целые числа без знака.
В этом разделе мы рассмотрим следующие темы:
Поэтому в этом разделе будет очень много кода на Rust. Я сделаю все возможное, чтобы приложить высокоуровневые описания того, что происходит в коде, чтобы вам не нужно было знать Rust, чтобы знать, что происходит. С учетом сказанного, чтобы получить максимальную отдачу от этого раздела, я бы порекомендовал прочитать отличную книгу по языку программирования Rust .
Кроме того, вам может быть полезно держать под рукой fstдокументацию по API , которая может служить хорошим дополнением к материалам в этом разделе.
Большинство структур данных в Rust изменяемы, что означает, что запросы, вставки и удаления аккуратно объединены в один API. Структуры данных, построенные на основе FST, описанных в этом сообщении в блоге, к сожалению, представляют собой другое животное, потому что после того, как они построены, их больше нельзя изменить. Таким образом, в API есть разделение, в котором различаются построение FST и запрос FST.
Это разделение отражено в типах, представленных fstбиблиотекой. Среди них есть Setи SetBuilder, где первый предназначен для запроса, а второй - для вставки. Карты имеют аналогичную дихотомию с Mapи MapBuilder.
Давайте перейдем к простому примеру, который создает набор и записывает его в файл. Действительно важным свойством этого кода является то, что набор записывается в файл по мере его создания. Ни в коем случае весь набор не сохраняется в памяти!
(Если вы не знакомы с Rust, я постарался быть немного подробным в комментариях.)
встроенный набор-файл
// Imports the `File` type into this scope and the entire `std::io` module.
use std::fs::File;
use std::io;
// Imports the `SetBuilder` type from the `fst` module.
use fst::SetBuilder;
// Create a file handle that will write to "set.fst" in the current directory.
let file_handle = File::create("set.fst")?;
// Make sure writes to the file are buffered.
let buffered_writer = io::BufWriter::new(file_handle);
// Create a set builder that streams the data structure to set.fst.
// We could use a socket here, or an in memory buffer, or anything that
// is "writable" in Rust.
let mut set_builder = SetBuilder::new(buffered_writer)?;
// Insert a few keys from the greatest band of all time.
// An insert can fail in one of two ways: either a key was inserted out of
// order or there was a problem writing to the underlying file.
set_builder.insert("bruce")?;
set_builder.insert("clarence")?;
set_builder.insert("stevie")?;
// Finish building the set and make sure the entire data structure is flushed
// to disk. After this is called, no more inserts are allowed. (And indeed,
// are prevented by Rust's type/ownership system!)
set_builder.finish()?;
(Если вы не знакомы с Rust, вы, вероятно, задаетесь вопросом: что это за чертовщина ?? Короче говоря, это оператор, который использует ранние возвраты и полиморфизм для обработки ошибок за нас. Лучший способ думать об этом is: каждый раз, когда вы видите ?, это означает, что базовая операция может завершиться неудачно, и если это произойдет, верните значение ошибки и прекратите выполнение текущей функции.Подробнее см. другую мою запись в блоге об обработке ошибок в Rust .
На высоком уровне это код:
Иногда, однако, нам не нужно передавать набор в файл на диске или не хотим. Иногда мы просто хотим встроить его в память и использовать. Это тоже возможно!
встроенный набор-память
use fst::{Set, SetBuilder};
// Create a set builder that streams the data structure to memory.
let mut set_builder = SetBuilder::memory();
// Inserts are the same as before.
// They can still fail if they are inserted out of order, but writes to the
// heap are (mostly) guaranteed to succeed. Since we know we're inserting these
// keys in the right order, we use "unwrap," which will panic or abort the
// current thread of execution if it fails.
set_builder.insert("bruce").unwrap();
set_builder.insert("clarence").unwrap();
set_builder.insert("stevie").unwrap();
// Finish building the set and get back a region of memory that can be
// read as an FST.
let fst_bytes = set_builder.into_inner()?;
// And create a new Set with those bytes.
// We'll cover this more in the next section on querying.
let set = Set::from_bytes(fst_bytes).unwrap();
Этот код в основном такой же, как и раньше, с двумя ключевыми отличиями:
Давайте теперь посмотрим на тот же процесс, но для карт. Это почти то же самое, за исключением того, что теперь мы вставляем значения с ключами:
билд-карта-памяти
use fst::{Map, MapBuilder};
// Create a map builder that streams the data structure to memory.
let mut map_builder = MapBuilder::memory();
// Inserts are the same as before, except we include a value with each key.
map_builder.insert("bruce", 1972).unwrap();
map_builder.insert("clarence", 1972).unwrap();
map_builder.insert("stevie", 1975).unwrap();
// These steps are exactly the same as before.
let fst_bytes = map_builder.into_inner()?;
let map = Map::from_bytes(fst_bytes).unwrap();
Это почти все, что нужно для построения упорядоченных наборов или карт, представленных FST. Есть документация по API как для наборов, так и для карт .
Ярлык для строителя
В приведенных выше примерах нам нужно было создать конструктор, вставить ключи один за другим, а затем, наконец, вызвать finishили into_innerдо того, как мы сможем объявить процесс построения набора или карты выполненным. Это часто удобно на практике (например, повторение строк в файле), но не так удобно для представления кратких примеров в сообщении блога. Поэтому воспользуемся небольшим удобством.
Следующий код создает набор в памяти:
встроенный набор-ярлык
use fst::Set; let set = Set::from_iter(vec!["bruce", "clarence", "stevie"])?;
Это даст тот же результат, что и раньше. Единственное отличие состоит в том, что мы выделяем динамически растущий вектор элементов до построения набора, что обычно не рекомендуется для больших данных.
Тот же трюк работает с картами, которые принимают последовательность кортежей (ключей и значений) вместо последовательности байтовых строк (ключей):
билд-карта-ярлык
use fst::Map;
let map = Map::from_iter(vec![
("bruce", 1972),
("clarence", 1972),
("stevie", 1975),
])?;
Построение структуры данных на основе FST - не совсем удобная модель. В частности, многие операции могут завершиться ошибкой, особенно при записи структуры данных непосредственно в файл. Следовательно, построение структуры данных на основе FST требует обработки ошибок.
К счастью, это не относится к запросам. Как только набор или карта построены, мы можем безрассудно бросать запросы.
Наборы простые. Ключевая операция: «Есть ли в наборе этот ключ?»
запрос-установка содержит
use fst::Set;
let set = Set::from_iter(vec!["bruce", "clarence", "stevie"])?;
assert!(set.contains("bruce")); // "bruce" is in the set
assert!(!set.contains("andrew")); // "andrew" is not
// Another obvious operation: how many elements are in the set?
assert_eq!(set.len(), 3);
Карты снова очень похожи, но мы также можем получить доступ к значению, связанному с ключом.
запрос-карта-прибудете
use fst::Map;
let map = Map::from_iter(vec![
("bruce", 1972),
("clarence", 1972),
("stevie", 1975),
])?;
// Maps have `contains_key`, which is just like a set's `contains`:
assert!(map.contains_key("bruce")); // "bruce" is in the map
assert!(!map.contains_key("andrew")); // "andrew" is not
// Maps also have `get`, which retrieves the value if it exists.
// `get` returns an `Option<u64>`, which is something that can either be
// empty (when the key does not exist) or present with the value.
assert_eq!(map.get("bruce"), Some(1972)); // bruce joined the band in 1972
assert_eq!(map.get("andrew"), None); // andrew was never in the band
Помимо простого тестирования членства и поиска ключей, наборы и карты также обеспечивают итерацию по своим элементам. Это упорядоченные наборы и карты, поэтому итерация дает элементы в лексикографическом порядке ключей.
запрос-набор потока
use std::str::from_utf8; // converts UTF-8 bytes to a Rust string
// We import the usual `Set`, but also include `Streamer`, which is a trait
// that makes it possible to call `next` on a stream.
use fst::{Streamer, Set};
// Store the keys somewhere so that we can compare what we get with them and
// make sure they're the same.
let keys = vec!["bruce", "clarence", "danny", "garry", "max", "roy", "stevie"];
// Pass a reference with `&keys`. If we had just used `keys` instead, then it
// would have *moved* into `Set::from_iter`, which would prevent us from using
// it below to check that the keys we got are the same as the keys we gave.
let set = Set::from_iter(&keys)?;
// Ask the set for a stream of all of its keys.
let mut stream = set.stream();
// Iterate over the elements and collect them.
let mut got_keys = vec![];
while let Some(key) = stream.next() {
// Keys are byte sequences, but the keys we inserted are strings.
// Strings in Rust are UTF-8 encoded, so we need to decode here.
let key = from_utf8(key)?.to_string();
got_keys.push(key);
}
assert_eq!(keys, got_keys);
(Если вы Rustacean и вам интересно, почему, черт возьми, мы используем while letздесь вместо forцикла или адаптера итератора, то пора открыть вам маленький грязный секрет: fstящик не раскрывает итераторы. Вместо этого он предоставляет потоки . Техническое обоснование подробно объясняется в документации по этому Streamer признаку .)
В этом примере мы запрашиваем набор для потока, что позволяет нам перебирать все ключи в наборе по порядку. Поток дает ссылку на внутренний буфер, поддерживаемый потоком. В Rust это совершенно безопасно, потому что система типов не позволит вам вызывать nextпоток, если ссылка на его внутренний буфер все еще жива (во время компиляции). Это означает, что вы, как потребитель, можете контролировать, все ли ключи хранятся в памяти (как в этом примере), или, если ваша задача требует только одного прохода по данным, вам никогда не нужно выделять место для каждого ключа. Этот стиль итерации называется потоковой передачей, потому что право собственности на элементы привязано к самой итерации.
Важно отметить, что этот процесс сильно отличается от других структур данных, таких как BTreeSet. Об этом говорит сайт https://intellect.icu . А именно, древовидная структура данных обычно имеет отдельное местоположение, выделенное для каждого ключа, поэтому она может просто возвращать ссылку на это распределение. То есть право собственности на элементы, полученное в результате итерации, привязано к структуре данных . Мы не можем достичь этого стиля итерации со структурами данных на основе FST без неприемлемых затрат на каждую итерацию. А именно, FST не хранит каждый ключ в своем собственном месте. Напомним из первой части этой статьи, что ключи хранятся в переходах конечного автомата. Следовательно, ключи создаются в процессе итерации .
Хорошо, вернемся к запросам. Помимо перебора всех ключей, мы также можем эффективно перебирать подмножество ключей с помощью запросов диапазона . Вот пример, основанный на предыдущем.
запрос-набор-диапазон
// We now need the IntoStreamer trait, which provides a way to convert a
// range query into a stream.
use fst::{IntoStreamer, Streamer, Set};
// Same as previous example.
let keys = vec!["bruce", "clarence", "danny", "garry", "max", "roy", "stevie"];
let set = Set::from_iter(&keys)?;
// Build a range query that includes all keys greater than or equal to `c`
// and less than or equal to `roy`.
let range = set.range().ge("c").le("roy");
// Turn the range into a stream.
let stream = range.into_stream();
// Use a convenience method defined on streams to collect the elements in the
// stream into a sequence of strings. This is effectively a shorter form of the
// `while let` loop we wrote out in the previous example.
let got_keys = stream.into_strs()?;
// Check that we got the right keys.
assert_eq!(got_keys, &keys[1..6]);
Ключевая строка в приведенном выше примере была такой:
let range = set.range().ge("c").le("roy");
Метод rangeвозвращает новый запрос диапазона, а также geи leметоды устанавливают тем больше, чем или равно и менее чем или равна часам, соответственно. Есть также gtи ltметоды, которые устанавливают больше, чем и менее чем в пределах, соответственно. Можно использовать любую комбинацию этих методов (если один используется более одного раза, последний заменяет предыдущий).
Как только запрос диапазона построен, его можно легко превратить в поток:
let stream = range.into_stream();
Когда у нас есть поток, мы можем перебирать его, используя nextметод и while letцикл, как мы видели в предыдущем примере. В этом примере вместо этого мы вызвали into_strsметод, который выполняет итерацию и декодирование UTF-8 за вас, возвращая результаты в векторе.
Те же методы доступны и на картах, за исключением того, что итерация дает кортежи ключей и значений вместо одного ключа.
Помните первый пример, в SetBuilderкотором мы передавали структуру данных прямо в файл? Оказывается, это действительно важный вариант использования структур данных на основе FST, особенно потому, что их рулевое управление - это огромные коллекции ключей. Возможность записывать структуру данных в том виде, в котором она построена, прямо на диск, не сохраняя всю структуру данных в памяти, - действительно хорошее удобство.
Можно ли что-то подобное сделать для чтения набора с диска? Конечно, можно открыть файл, прочитать его содержимое и использовать его для создания Set:
читать посаженные-ММАП
use std::fs::File;
use std::io::Read;
use fst::Set;
// Open a handle to a file and read its entire contents into memory.
let mut file_handle = File::open("set.fst")?;
let mut bytes = vec![];
file_handle.read_to_end(&mut bytes)?;
// Construct the set.
let set = Set::from_bytes(bytes)?;
// Finally, we can query.
println!("number of elements: {}", set.len());
Дорогостоящая часть этого кода - считывание всего файла в память. Звонок на Set::from_bytesсамом деле довольно быстрый. Он считывает небольшую часть метаданных, закодированных в FST, и вычисляет упрощенную контрольную сумму. Фактически, для этого процесса требуется всего 32 байта!
Один из возможных способов смягчить это - научить структуру данных FST читать непосредственно из файла. В частности, он будет знать, что нужно выполнять seekсистемные вызовы, чтобы перемещаться по файлу для обхода конечного автомата. К сожалению, это может быть слишком дорого, потому что звонки seekбудут происходить очень часто. Каждый seekвлечет за собой накладные расходы на системный вызов, которые, вероятно, сделают поиск FST чрезмерно медленным.
Другой способ смягчить это - поддерживать ограниченный по размеру кеш, в котором в памяти хранятся фрагменты файла, но, вероятно, не все. Когда необходимо получить доступ к области файла, которая не находится в кэше, фрагмент файла, который включает эту область, считывается и добавляется в кеш (возможно, удаляя фрагмент, к которому не было доступа в течение некоторого времени). Когда мы снова обращаемся к этой области, и она уже находится в кеше, никакого ввода-вывода не требуется. Такой подход также позволяет нам понять, что хранится в памяти. А именно, мы могли бы убедиться, что все фрагменты, близкие к начальному состоянию машины, находятся в кеше, поскольку теоретически к ним будут чаще всего обращаться. К сожалению, этот подход сложен в реализации и имеет другие проблемы .
Третий способ - это так называемый файл с отображением памяти . Когда создается файл с отображением в память, он открывается нам, как если бы это была последовательность байтов в памяти. Когда мы обращаемся к этой области памяти, возможно, что там еще нет реальных данных из файла для чтения. Это вызывает ошибку страницы, которая сообщает операционной системе, что нужно прочитать фрагмент из файла и сделать его доступным для использования в последовательности байтов, представленных программе. Операционная система затем отвечает за то, какие части файла фактически находятся в памяти. Фактический процесс чтения данных из файла и сохранения их в памяти прозрачен для нашей программы - все, что fstвидит ящик, - это обычная последовательность байтов.
Этот третий способ на самом деле очень похож на нашу идею выше с кешем. Ключевое отличие состоит в том, что операционная система управляет кешем вместо нас. Это резкое упрощение в реализации. Конечно, есть определенные затраты. Поскольку операционная система управляет кешем, она не может знать, что определенные части FST всегда должны оставаться в памяти. Поэтому иногда у нас может не быть оптимального времени запроса. Эти недостатки можно несколько смягчить за счет использования таких вызовов, как mlockили madvise, которые позволяют вашему процессу сообщать операционной системе, что определенные области карты памяти должны оставаться в памяти или вне ее.
fstКлеть поддерживает использование памяти карты (но еще не использовать mlockили madvise). Вот наш предыдущий пример, но измененный для использования карты памяти:
чтения набор-файлы
use fst::Set;
// Construct the set from a file path. The fst crate implements this using a
// memory map, which is why this method is unsafe to call. Callers must ensure
// that they do not open another mutable memory map in the same program.
let set = unsafe { Set::from_path("set.fst")? };
// Finally, we can query. This can happen immediately, without having
// to read the entire set into memory.
println!("number of elements: {}", set.len());
Это все, что нужно сделать. Запросы остаются прежними. Тот факт, что используется карта памяти, полностью прозрачен для вашей программы.
Здесь стоит упомянуть еще об одной стоимости. Формат, используемый для представления FST в памяти, способствует произвольному доступу к данным. А именно, поиск клавиши может перескакивать в разные области FST, которые совсем не близки друг к другу. Это означает, что чтение FST с диска через карту памяти может быть дорогостоящим, поскольку ввод-вывод с произвольным доступом выполняется медленно. Это особенно верно при использовании нетвердотельного диска, поскольку для произвольного доступа потребуется много физического поиска. Если вы оказались в такой ситуации, и кеш страниц операционной системы не может компенсировать это, вам может потребоваться оплатить аванс и загрузить весь FST в память. Обратите внимание, что это не совсем смертный приговор, поскольку цель FST - быть очень маленькой. Например, FST с миллионами ключей может уместиться в несколько мегабайт памяти. (например, Все 3.
При наличии набора строк очень полезной операцией является нечеткий поиск . Существует много различных типов нечеткого поиска, но здесь мы рассмотрим только один: нечеткий поиск по Левенштейну или расстояние «редактирования».
Расстояние Левенштейна - это способ сравнения двух строк. А именно, учитывая строку A и B, Левенштейн расстояние Aи Bэто количество символов вставок, удалений и замен необходимо выполнить , чтобы преобразовать Aв B. Вот несколько простых примеров:
Существует множество способов реализовать алгоритм, вычисляющий расстояние Левенштейна между двумя строками. В первом приближении лучшее, что можно сделать, - это O(mn)время, где mи n- длины сравниваемых строк.
Для наших целей вопрос, на который мы хотели бы ответить: соответствует ли этот ключ любому из ключей в настройке с расстоянием Левенштейна, равным n?
Конечно, мы могли бы реализовать алгоритм для вычисления расстояния Левенштейна между двумя строками, перебрать ключи в одном из наших упорядоченных наборов на основе FST и запустить алгоритм для каждого ключа. Если расстояние между запросом и ключом равно <= n, то мы выдаем его как совпадение. В противном случае мы пропускаем ключ и переходим к следующему.
Проблема с этим подходом в том, что он невероятно медленный. Это требует запуска эффективного квадратичного алгоритма для каждого ключа в наборе. Не хорошо.
Оказывается, для нашего конкретного случая использования мы можем сделать намного лучше. А именно, в нашем случае одна из строк в каждом вычислении расстояния для одного поиска является фиксированной ; запрос остается прежним. Учитывая эти условия и известный порог расстояния, мы можем построить автомат, который распознает все строки, соответствующие нашему запросу.
Почему это полезно? Что ж, наш упорядоченный набор на основе FST - это автомат! Это означает, что ответ на вопрос с помощью нашего упорядоченного множества ничем не отличается от пересечения двух автоматов. Это действительно быстро.
Вот быстрый пример, демонстрирующий нечеткий поиск по упорядоченному набору.
Левенштейн
// We've seen all these imports before except for Levenshtein.
// Levenshtein is a type that knows how to build Levenshtein automata.
use fst::{IntoStreamer, Streamer, Set};
use fst_levenshtein::Levenshtein;
let keys = vec!["fa", "fo", "fob", "focus", "foo", "food", "foul"];
let set = Set::from_iter(keys)?;
// Build our fuzzy query. This says to search for "foo" and return any keys
// that have a Levenshtein distance from "foo" of no more than 1.
let lev = Levenshtein::new("foo", 1)?;
// Apply our fuzzy query to the set we built and turn the query into a stream.
let stream = set.search(lev).into_stream();
// Get the results and confirm that they are what we expect.
let keys = stream.into_strs()?;
assert_eq!(keys, vec![
"fo", // 1 deletion
"fob", // 1 substitution
"foo", // 0 insertions/deletions/substitutions
"food", // 1 insertion
]);
Действительно важным свойством использования автомата для поиска в нашем наборе является то, что он может эффективно исключать целые области нашего набора для поиска. А именно, если наш запрос имеет foodпороговое значение расстояния 1, то он никогда не будет посещать ключи в базовом FST с длиной, превышающей 5точно, потому что такие ключи никогда не будут соответствовать нашим критериям поиска. Он также может пропускать многие другие клавиши, например, любые клавиши, начинающиеся с двух букв, которые не являются ни fили o. Такие ключи также никогда не могут соответствовать нашим критериям поиска, потому что они уже превышают пороговое значение расстояния.
К сожалению, обсуждение того, как именно реализованы автоматы Левенштейна, выходит за рамки данной статьи. Реализация частично основана на идеях Жюля Джейкобса . Однако есть часть этой реализации, о которой стоит поговорить: Unicode.
В предыдущем разделе мы видели пример кода, который строит автомат Левенштейна , который можно использовать для нечеткого поиска упорядоченного набора или карты в fstкорзине.
Действительно важная деталь, которую мы упустили, - это то, как на самом деле определяется расстояние Левенштейна. Вот то, что я сказал, с добавлением акцента:
Расстояние Левенштейна - это способ сравнения двух строк. А именно, учитывая строку Aи B, Левенштейн расстояние Aи Bэто количество символов вставок, удалений и замен необходимо выполнить , чтобы преобразовать Aв B.
Что такое «персонаж» и как с ним справляются наши упорядоченные наборы и карты на основе FST? Нет единого верного канонического определения того, что такое персонаж, и поэтому это был плохой выбор слов для технических умов. Лучшее слово, которое отражает реальную реализацию, - это количество кодовых точек Unicode . То есть расстояние Левенштейна - это количество вставок, удалений или замен кодовых точек Unicode для преобразования одного ключа в другой.
К сожалению, здесь недостаточно места, чтобы перейти к Unicode, но « Введение в Unicode» - это информативное чтение, в котором кратко определяется важная терминология. Репортаж Дэвида С. Зентграфа тоже хорош, но намного длиннее и подробнее. Важными моментами являются следующие:
Наш выбор использования кодовых точек - это естественный компромисс между правильностью, сложностью реализации и производительностью. Самый простой способ реализовать - это предположить, что каждый символ представлен одним байтом. Но что происходит, когда ключ содержит ☃(снеговика Unicode, который представляет собой единственную кодовую точку), который закодирован как 3 байта в UTF-8? Пользователь видит его как одиночный символ, но автомат Левенштейна будет рассматривать его как 3 символа. Это плохо.
Поскольку наши FST действительно основаны на байтах (т.е. каждый переход в преобразователе соответствует ровно одному байту), это означает, что наш автомат Левенштейна должен иметь встроенное декодирование UTF-8 . Написанная мною реализация основана на уловке, которую использовал Расс Кокс для RE2 (который, в свою очередь, получил ее от Кена Томпсона grep). Подробнее об этом можно прочитать в документации utf8-rangesобрешетки.
Действительно классное свойство, которое выпадает из этого подхода, заключается в том, что если вы выполните запрос Левенштейна с использованием этого ящика, то все ключи гарантированно будут действительными UTF-8. Если ключ недействителен UTF-8, автомат Левенштейна просто не сможет сопоставить его.
Другой тип запроса, который мы можем захотеть выполнить для наших структур данных на основе FST, - это регулярное выражение . Проще говоря, регулярное выражение - это простой синтаксис шаблона, описывающий регулярные языки. Например, регулярное выражение [0-9]+(foo|bar)соответствует любому тексту, который начинается с одной или нескольких числовых цифр, за которыми следует либо fooили bar.
Конечно, было бы неплохо искать в наших наборах или картах, используя регулярное выражение. Один из способов сделать это - перебрать все ключи и применить регулярное выражение к каждому ключу. Если совпадений нет, пропустите ключ. К сожалению, это будет довольно медленно. Регулярные выражения Rust не сутулиться, но выполнение регулярного выражения миллионы раз на небольших строках обязательно будет медленным. Что еще более важно, используя этот подход, мы должны посетить каждую клавишу в наборе. Для большого набора это может сделать запрос регулярного выражения невозможным.
Как и в случае с вычислением расстояния Левенштейна в предыдущем разделе, оказывается, что мы можем сделать намного лучше. А именно, поскольку наше регулярное выражение остается неизменным на протяжении всего поиска, мы можем предварительно вычислить автомат, который знает, как сопоставить любой текст с регулярным выражением. Поскольку наши наборы и карты сами по себе являются автоматами, это означает, что мы можем очень эффективно искать наши структуры данных, пересекая два автомата.
Вот простой пример:
регулярное выражение
// We've seen all these imports before except for Regex.
// Regex is a type that knows how to build regular expression automata.
use fst::{IntoStreamer, Streamer, Set};
use fst_regex::Regex;
let keys = vec!["123", "food", "xyz123", "τροφή", "еда", "מזון", "☃☃☃"];
let set = Set::from_iter(keys)?;
// Build a regular expression. This can fail if the syntax is incorrect or
// if the automaton becomes too big.
// This particular regular expression matches keys that are not empty and
// only contain letters. Use of `\pL` here stands for "any Unicode codepoint
// that is considered a letter."
let lev = Regex::new(r"\pL+")?;
// Apply our regular expression query to the set we built and turn the query
// into a stream.
let stream = set.search(lev).into_stream();
// Get the results and confirm that they are what we expect.
let keys = stream.into_strs()?;
// Notice that "123", "xyz123" and "☃☃☃" did not match.
assert_eq!(keys, vec![
"food",
"τροφή",
"еда",
"מזון",
]);
В этом примере мы показываем, как выполнить запрос регулярного выражения для упорядоченного набора. Регулярное выражение \pL+, которое будет соответствовать только непустым ключам, которые соответствуют последовательности кодированных кодовых точек UTF-8, которые считаются буквами. Такие цифры, как 2и такие классные символы, как ☃(снеговик в Юникоде), не считаются буквами, поэтому ключи, содержащие эти символы, не соответствуют нашему регулярному выражению.
Запросы с регулярным выражением имеют два важных сходства с запросами Левенштейна:
Как и в случае с автоматами Левенштейна, мы, к сожалению, не будем говорить о том, как автомат реализован. На самом деле это довольно большая тема, и серия статей Рассса Кокса по этой теме является авторитетной. Также стоит отметить, что благодаря regex-syntax обрешетке это было реально сделать. Таким образом, мы гарантированно будем использовать тот же синтаксис, что и regex ящик Rust . (Парсер регулярных выражений часто является одним из наиболее сложных аспектов реализации!)
И последнее замечание: очень легко написать регулярное выражение, сопоставление которого с большим набором займет много времени. Например, если регулярное выражение начинается с .*(что означает «совпадение нуля или более кодовых точек Unicode»), то это, вероятно, приведет к обращению к каждому ключу в автомате.
И последнее, о чем мы должны поговорить, чтобы завершить базовые запросы: операции с наборами. Ящик поддерживает некоторые общие операции над fstнаборами: объединение, пересечение, разность и симметричная разность. Все эти операции могут эффективно работать с любым количеством наборов или карт .
Это особенно полезно, если у вас есть несколько наборов или карт на диске, которые вы хотите найти. Поскольку fstящик поддерживает их отображение в памяти, это означает, что мы можем искать множество наборов почти мгновенно.
Давайте посмотрим на пример, который выполняет поиск по нескольким FST и объединяет результаты поиска в один поток.
setop
use std::str::from_utf8;
use fst::{Streamer, Set};
use fst::set;
// Create 5 sets. As a convenience, these are stored in memory, but they could
// just as easily have been memory mapped from disk using `Set::from_path`.
let set1 = Set::from_iter(&["AC/DC", "Aerosmith"])?;
let set2 = Set::from_iter(&["Bob Seger", "Bruce Springsteen"])?;
let set3 = Set::from_iter(&["George Thorogood", "Golden Earring"])?;
let set4 = Set::from_iter(&["Kansas"])?;
let set5 = Set::from_iter(&["Metallica"])?;
// Build a set operation. All we need to do is add a stream from each set and
// ask for the union. (Other operations, such as `intersection`, are also
// available.)
let mut stream =
set::OpBuilder::new()
.add(&set1)
.add(&set2)
.add(&set3)
.add(&set4)
.add(&set5)
.union();
// Now collect all of the keys. `stream` is just like any other stream that
// we've seen before.
let mut keys = vec![];
while let Some(key) = stream.next() {
let key = from_utf8(key)?.to_string();
keys.push(key);
}
assert_eq!(keys, vec![
"AC/DC", "Aerosmith", "Bob Seger", "Bruce Springsteen",
"George Thorogood", "Golden Earring", "Kansas", "Metallica",
]);
В этом примере в памяти создается 5 различных наборов, создается новая операция набора, добавляется поток из каждого набора в сборку, а затем запрашивается объединение всех потоков.
Операция unionset, как и все остальные, реализована в потоковом режиме. То есть ни одна из операций не требует сохранения всех ключей в памяти именно потому, что ключи в каждом наборе упорядочены. (Фактическая реализация использует структуру данных, называемую двоичной кучей .)
Самое замечательное в потоках то, что они могут быть составлены. В частности, было бы очень грустно, если бы вы ограничились только объединением целых наборов. Вместо этого вы можете фактически выполнить любой тип запроса по наборам и взять объединение.
Вот тот же пример, что и выше, но с регулярным выражением, которое сопоставляет только ключи с хотя бы одним пробелом в них:
setop-регулярное выражение
use std::str::from_utf8;
use fst::{Streamer, Set};
use fst::set;
use fst_regex::Regex;
// Create 5 sets. As a convenience, these are stored in memory, but they could
// just as easily have been memory mapped from disk using `Set::from_path`.
let set1 = Set::from_iter(&["AC/DC", "Aerosmith"])?;
let set2 = Set::from_iter(&["Bob Seger", "Bruce Springsteen"])?;
let set3 = Set::from_iter(&["George Thorogood", "Golden Earring"])?;
let set4 = Set::from_iter(&["Kansas"])?;
let set5 = Set::from_iter(&["Metallica"])?;
// Build our regular expression query.
let spaces = Regex::new(r".*\s.*")?;
// Build a set operation. All we need to do is add a stream from each set and
// ask for the union. (Other operations, such as `intersection`, are also
// available.)
let mut stream =
set::OpBuilder::new()
.add(set1.search(&spaces))
.add(set2.search(&spaces))
.add(set3.search(&spaces))
.add(set4.search(&spaces))
.add(set5.search(&spaces))
.union();
// This is the same as the previous example, except our search narrowed our
// results down a bit.
let mut keys = vec![];
while let Some(key) = stream.next() {
let key = from_utf8(key)?.to_string();
keys.push(key);
}
assert_eq!(keys, vec![
"Bob Seger", "Bruce Springsteen", "George Thorogood", "Golden Earring",
]);
Построение операции набора работает с любым типом потока. Некоторые потоки могут быть запросами регулярных выражений, другие - запросами Левенштейна, а третьи - запросами диапазона.
В этом разделе рассматриваются наборы, но мы не учли карты. Карты несколько сложнее, потому что поток, созданный операцией set над ключами карты, также должен включать значения, связанные с каждым ключом. В частности, для операции объединения каждый ключ, испущенный в потоке, мог встречаться более чем в одной из указанных карт. Я fstвоспользуюсь документацией по API для объединения карт , которая содержит пример.
Все примеры кода, которые мы видели до сих пор, использовали типы данных Setили Mapв fstящике. На самом деле, реализация Setor не представляет особого интереса Map, поскольку обе они просто обертывают Fstтип. Действительно, их представление:
// The Fst type is tucked away in the `raw` sub-module. use fst::raw::Fst; // These type declarations define sets and maps as nothing more than structs // with a single member: an Fst. pub struct Set(Fst); pub struct Map(Fst);
Другими словами, в Fstтипе и заключается все действие. По большей части создание Fst и его запросы следуют тому же шаблону, что и наборы и карты. Вот пример:
FST-сборки
use fst::raw::{Builder, Fst, Output};
// The Fst type has a separate builder just like sets and maps.
let mut builder = Builder::memory();
builder.insert("bar", 1).unwrap();
builder.insert("baz", 2).unwrap();
builder.insert("foo", 3).unwrap();
// Finish construction and get the raw bytes of the fst.
let fst_bytes = builder.into_inner()?;
// Create an Fst that we can query.
let fst = Fst::from_bytes(fst_bytes)?;
// Basic querying.
assert!(fst.contains_key("foo"));
assert_eq!(fst.get("abc"), None);
// Looking up a value returns an `Output` instead of a `u64`.
// This is the internal representation of an output on a transition.
// The underlying u64 can be accessed with the `value` method.
assert_eq!(fst.get("baz"), Some(Output::new(2)));
// Methods like `stream`, `range` and `search` are also available, which
// function the same way as they do for sets and maps.
Если вы следовали инструкциям, этот код к настоящему времени должен выглядеть в основном знакомым. Одним из ключевых отличие заключается в том , что getвозвращает Outputвместо того , чтобы u64. OutputПодвергаются воздействие , потому что это внутреннее представление выхода на переходе в конечном преобразователе. Если outесть тип Output, то можно получить базовое числовое значение, позвонив out.value().
Ключевой особенностью этого Fstтипа является доступ к лежащему в основе конечному автомату. А именно, у этого Fstтипа вам доступны два важных метода:
Узлы предоставляют возможность пройти все его переходы и спросить, является ли это конечным состоянием или нет. Например, рассмотрите возможность запуска пути для отслеживания ключа bazчерез машину:
FST-узел
use fst::raw::{Builder, Fst};
let mut builder = Builder::memory();
builder.insert("bar", 1).unwrap();
builder.insert("baz", 2).unwrap();
builder.insert("foo", 3).unwrap();
let fst_bytes = builder.into_inner()?;
let fst = Fst::from_bytes(fst_bytes)?;
// Get the root node of this FST.
let root = fst.root();
// Print the transitions out of the root node in lexicographic order.
// Outputs "b" followed by "f."
for transition in root.transitions() {
println!("{}", transition.inp as char);
}
// Find the position of a transition based on the input.
let i = root.find_input(b'b').unwrap();
// Get the transition.
let trans = root.transition(i);
// Get the node that the transition points to.
let node = fst.node(trans.addr);
// And so on...
С помощью этих инструментов мы действительно можем показать, как реализовать contains_key метод!
FST-содержит
use fst::raw::Fst;
// The function takes a reference to an Fst and a key and returns true if
// and only if the key is in the Fst.
fn contains_key(fst: &Fst, key: &[u8]) -> bool {
// Start the search at the root node.
let mut node = fst.root();
// Iterate over every byte in the key.
for b in key {
// Look for a transition in this node for this byte.
match node.find_input(*b) {
// If one cannot be found, we can conclude that the key is not
// in this FST and quit early.
None => return false,
// Otherwise, we set the current node to the node that the found
// transition points to. In other words, we "advance" the finite
// state machine.
Some(i) => {
node = fst.node(node.transition_addr(i));
}
}
}
// After we've exhausted the key to look up, it is only in the FST if we
// ended at a final state.
node.is_final()
}
И это почти все, что нужно сделать. NodeТип имеет несколько более полезных документированных методов , которые вы можете захотеть просмотреть.
Исследование, описанное в статье про Библиотека FST, подчеркивает ее значимость в современном мире. Надеюсь, что теперь ты понял что такое Библиотека FST и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Индексирование большого набора ключей с помощью конечных автоматов
Комментарии
Оставить комментарий
Индексирование большого набора ключей с помощью конечных автоматов
Термины: Индексирование большого набора ключей с помощью конечных автоматов