प्रत्यय ऐरे और q -ग्राम अनुक्रमणिका
यदि आपके तारों के आकार पर सख्त ऊपरी सीमा है तो आप प्रत्यय सरणी : केवल एक विशेष चरित्र (जैसे नल चार) का उपयोग करके अपने सभी तारों को उसी अधिकतम लंबाई तक पैड करें। फिर सभी तारों को संयोजित करें और उन पर एक प्रत्यय सरणी अनुक्रमणिका बनाएं।
This gives you a lookup runtime of m * log n where m is the length of your query string and n is the overall length of your combined strings. If this still isn't good enough and your m has a fixed, small length, and your alphabet Σ is restricted in size (say, Σ < 128 different characters) you can additionally build a q-gram index. This will allow retrieval in constant time. However, the q-gram table requires Σm entries (= 8 MiB in the case of just 3 characters, and 1 GiB for 4 characters!).
सूचकांक को छोटा बनाना
हैश फ़ंक्शन को समायोजित करके q -gram तालिका (घातीय रूप से, सर्वोत्तम मामले में) के आकार को कम करना संभव हो सकता है। प्रत्येक संभावित q -gram के लिए एक अद्वितीय संख्या असाइन करने के बजाय आप एक हानिकारक हैश फ़ंक्शन को नियोजित कर सकते हैं। तब तालिका को सटीक मिलान के अनुरूप केवल एक प्रत्यय सरणी प्रविष्टि के बजाय संभावित प्रत्यय सरणी सूचकांक की सूचियां संग्रहित करनी होंगी। यह होगा कि लुकअप अब स्थिर नहीं है, हालांकि, सूची में सभी प्रविष्टियों पर विचार करना होगा।
वैसे, मुझे यकीन नहीं है कि आप कैसे q -gram अनुक्रमणिका काम करता है से परिचित हैं क्योंकि इंटरनेट इस विषय पर सहायक नहीं है। मैंने पहले किसी अन्य विषय में इसका उल्लेख किया है। इसलिए मैंने अपने बैचलर थीसिस में निर्माण के लिए एक विवरण और एक एल्गोरिदम शामिल किया है।
अवधारणा के सुबूत
I've written a very small C# अवधारणा के सुबूत (since you stated otherwise that you worked with C#). It works, however it is very slow for two reasons. First, the suffix array creation simply sorts the suffixes. This alone has runtime n2 log n. There are far superior methods. Worse, however, is the fact that I use SubString to obtain the suffixes. Unfortunately, .NET creates copies of the whole suffix for this. To use this code in practice, make sure that you use in-place methods which do not copy any data around unnecessarily. The same is true for retrieving the q-grams from the string.
मेरे उदाहरण में उपयोग की जाने वाली m_Data स्ट्रिंग का निर्माण करना संभवतः बेहतर होगा। इसके बजाय, आप मूल सरणी के संदर्भ को सहेज सकते हैं और इस सरणी पर काम करके मेरे सभी SubString accesss को अनुकरण कर सकते हैं।
फिर भी, यह देखना आसान है कि इस कार्यान्वयन ने अनिवार्य रूप से निरंतर समय पुनर्प्राप्ति की उम्मीद की है (यदि शब्दकोश अच्छी तरह से व्यवहार किया जाता है)! यह काफी उपलब्धि है जिसे खोज पेड़/ट्राई द्वारा संभवतः पीटा नहीं जा सकता है!
class QGramIndex {
private readonly int m_Maxlen;
private readonly string m_Data;
private readonly int m_Q;
private int[] m_SA;
private Dictionary m_Dir = new Dictionary();
private struct StrCmp : IComparer {
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 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);
}
}