Суффиксный массив и q -граммный индекс
Если ваши строки имеют строгую верхнюю границу размера, вы можете рассмотреть использование массива суффиксов : просто добавьте все свои строки к одной максимальной длине, используя специальный символ (например, нулевой символ). Затем объедините все строки и создайте для них индекс массива суффиксов.
Это дает вам время выполнения поиска m * log n , где m - длина строки запроса, а n - общая длина ваших комбинированных строк. Если это все еще недостаточно, и ваш m имеет фиксированную небольшую длину и ваш алфавит Σ ограничен в размерах (скажем, Σ <128 различных символов), вы можете дополнительно создать <strong> q -граммный индекс . Это позволит искать в постоянное время . Однако для таблицы q -грамм требуется Σ m записей (= 8 МБ для 3 символов и 1 ГБ для 4 символов!).
Уменьшение индекса
Можно уменьшить размер таблицы q -грамм (в лучшем случае экспоненциально), отрегулировав хеш-функцию. Вместо присвоения уникального номера каждой возможной q -грамме вы можете использовать хэш-функцию с потерями. В этой таблице необходимо хранить списки возможных индексов суффиксного массива вместо одной записи суффиксного массива, соответствующей точному совпадению. Это повлечет за собой, что поиск больше не является постоянным, потому что все записи в списке должны быть рассмотрены.
Кстати, я не уверен, если вы знакомы с , как индекс q -грамм работает , поскольку Интернет не помогает в этой теме. Я упоминал об этом раньше в другой теме. Поэтому я включил описание и алгоритм построения в мою дипломную работу бакалавра .
Подтверждение концепции
Я написал очень маленькое подтверждение концепции C # (поскольку вы заявили иначе, что работали с C #). Это работает, однако это очень медленно по двум причинам. Во-первых, создание массива суффиксов просто сортирует суффиксы. Одно это имеет время выполнения n 2 log n . Есть намного лучшие методы. Хуже всего то, что я использую SubString для получения суффиксов. К сожалению, .NET создает копии всего суффикса для этого. Чтобы использовать этот код на практике, убедитесь, что вы используете методы на месте, которые не копируют никакие данные без необходимости. То же самое верно для извлечения q -грамм из строки.
Возможно, даже лучше не создавать строку m_Data, использованную в моем примере. Вместо этого вы можете сохранить ссылку на исходный массив и смоделировать все мои SubString обращения, работая с этим массивом.
Тем не менее, легко заметить, что эта реализация, по сути, ожидала получения с постоянным временем (если словарь хорошо себя ведет)! Это настоящее достижение, которое невозможно превзойти с помощью дерева поиска / trie!
class QGramIndex {
private readonly int m_Maxlen;
private readonly string m_Data;
private readonly int m_Q;
private int[] m_SA;
private Dictionary<string, int> m_Dir = new Dictionary<string, int>();
private struct StrCmp : IComparer<int> {
public readonly String Data;
public StrCmp(string data) { Data = data; }
public int Compare(int x, int y) {
return string.CompareOrdinal(Data.Substring(x), Data.Substring(y));
}
}
private readonly StrCmp cmp;
public QGramIndex(IList<string> strings, int maxlen, int q) {
m_Maxlen = maxlen;
m_Q = q;
var sb = new StringBuilder(strings.Count * maxlen);
foreach (string str in strings)
sb.AppendFormat(str.PadRight(maxlen, '\u0000'));
m_Data = sb.ToString();
cmp = new StrCmp(m_Data);
MakeSuffixArray();
MakeIndex();
}
public int this[string s] { get { return FindInIndex(s); } }
private void MakeSuffixArray() {
// Approx. runtime: n^3 * log n!!!
// But I claim the shortest ever implementation of a suffix array!
m_SA = Enumerable.Range(0, m_Data.Length).ToArray();
Array.Sort(m_SA, cmp);
}
private int FindInArray(int ith) {
return Array.BinarySearch(m_SA, ith, cmp);
}
private int FindInIndex(string s) {
int idx;
if (!m_Dir.TryGetValue(s, out idx))
return -1;
return m_SA[idx] / m_Maxlen;
}
private string QGram(int i) {
return i > m_Data.Length - m_Q ?
m_Data.Substring(i) :
m_Data.Substring(i, m_Q);
}
private void MakeIndex() {
for (int i = 0; i < m_Data.Length; ++i) {
int pos = FindInArray(i);
if (pos < 0) continue;
m_Dir[QGram(i)] = pos;
}
}
}
Пример использования:
static void Main(string[] args) {
var strings = new [] { "hello", "world", "this", "is", "a",
"funny", "test", "which", "i", "have",
"taken", "much", "too", "far", "already" };
var index = new QGramIndex(strings, 10, 3);
var tests = new [] { "xyz", "aki", "ake", "muc", "uch", "too", "fun", "est",
"hic", "ell", "llo", "his" };
foreach (var str in tests) {
int pos = index[str];
if (pos > -1)
Console.WriteLine("\"{0}\" found in \"{1}\".", str, strings[pos]);
else
Console.WriteLine("\"{0}\" not found.", str);
}
}