othman:search
اختلافات
عرض الاختلافات بين النسخة المختارة و النسخة الحالية من الصفحة.
جانبي المراجعة السابقةالمراجعة السابقةالمراجعة التالية | المراجعة السابقة | ||
othman:search [2010/04/24 20:24] – alsadi | othman:search [2015/04/23 03:21] (حالي) – تحرير خارجي 127.0.0.1 | ||
---|---|---|---|
سطر 1: | سطر 1: | ||
+ | ====== محرك البحث في النّص القرآني ====== | ||
+ | يُفترض أن يستخدم محرّك البحث مجموعة من الخوارزميات المحسّنة المصمّمة خصيصاً للنّص القرآني بحيث نوفّر الوقت والحجم (أي حجم الفهرس). | ||
+ | |||
+ | والمقصود بالبحث هنا هو البحث في النّص القرآني بالرّسم الإملائي المضبوط بقراءة حفص عن عاصم. | ||
+ | |||
+ | ===== طرق التحسين العامة ===== | ||
+ | * لا نحتاج لإدارة عمليات الإضافة والحذف فهذه العملية تتم مرة واحدة عند بناء الحزمة لثبات النص. | ||
+ | * لا يهتم من يبحث في النّص القرآني عن ترتيب (rank)للنتائج بل يريدها حسب مكان ورودها في المصحف لأن النّاس تتذكّر النّص القرآني حرفيا. | ||
+ | * ترقيم الآيات واحدة بعد الأخرى يعني الآية التاسعة (رقم 8) هي الآية الثانية من سورة البقرة (نعلم ذلك بعمل bisect للعدد التراكمي للآيات في السور: يعني: 7 ثم 7+286 ثم 7+286+200 وهكذا) | ||
+ | * عمل bit field مكون من 6236 بت كل واحد يمثل آية (أي 780 بايت) | ||
+ | * تجذيع الكلمات ولكل كلمة نعمل كائن من النّوع السابق يمثّل أماكن ورودها ب 1 في البت المقابل للآية. | ||
+ | * إن أردنا البحث عن العبارات (كلمات متتابعة) وليس الكلمات يمكن: | ||
+ | - استخراج نتائج البحث عن الكلمات ثم عمل بحث غير مفهرس فيها | ||
+ | - أو يمكن الاحتفاظ ب term vector مقابل كل كلمة | ||
+ | * أكبر عدد من الكلمات في الآية 129 وهو في آية الدَّين في سورة البقرة وهذا يعني أن بايت واحد يكفي لتمثيل الكلمة في الآية. | ||
+ | * يستحيل أن تتكرّر الكلمة أكثر من 129 مرة في الآية الواحدة (للسبب السابق) أي أن بايت واحد يكفي لبيان عدد مرّات ورود الكلمة في الآية | ||
+ | * يتكوّن term vector من: | ||
+ | * تكرار الكلمة في كل آية تحتوي الكلمة مثلا 1 ثم 2 ثم 1 ثم 1 تعني أن الكلمة وردت 5 مرات. | ||
+ | * قائمة بأرقام الكلمات وفي المثال نحتاج 5 أرقام. | ||
+ | |||
+ | ===== طرق التفيذ ===== | ||
+ | حاولت مقاومة استعمال sqlite حيث ظننت أن عمل ملف باستعمال struct سيفيد إلاّ أنّي في النّهاية استعملت قائمة بأرقام الآيات محفوظة في sqlite | ||
+ | |||
+ | ==== قائمة أرقام الآيات ==== | ||
+ | من التبذير تخصيص 1 بت لكل آية في كل كلمة حيث أن كلمة مثل " | ||
+ | |||
+ | فإن استخدمنا الكلمة ثمّ : ثمّ رقم الآية فسيكون حجم الملف نصف ميغابايت وإن استعملنا 16-بت لتمثيل رقم الآية سيكون حجم الفهرس 300 كيلوبايت. | ||
+ | |||
+ | وبعد عملها على شكل sqlite كان حجم الملف تقريبا 750 كيلوبابت لكنّنا في هذه الحالة كسبنا البحث عن جزء من الكلمة. | ||
+ | |||
+ | لتسريع عمليات و/أو استخدمت set في بايثون. | ||
+ | |||
+ | ==== حقل البتات لكل آية ==== | ||
+ | === الكود === | ||
+ | تمّ تجربة ذلك في إصدارة قديمة ذات [[http:// | ||
+ | وهذا [[http:// | ||
+ | |||
+ | <code python> | ||
+ | normalize_tb={ | ||
+ | 65: 97, 66: 98, 67: 99, 68: 100, 69: 101, 70: 102, 71: 103, 72: 104, 73: 105, 74: 106, 75: 107, 76: 108, 77: 109, 78: 110, 79: 111, 80: 112, 81: 113, 82: 114, 83: 115, 84: 116, 85: 117, 86: 118, 87: 119, 88: 120, 89: 121, 90: 122, | ||
+ | 1600: None, 1569: 1575, 1570: 1575, 1571: 1575, 1572: 1575, 1573: 1575, 1574: 1575, 1577: 1607, 1611: None, 1612: None, 1613: None, 1614: None, 1615: None, 1616: None, 1617: None, 1618: None, 1609: 1575} | ||
+ | |||
+ | def normalize(s): | ||
+ | |||
+ | class searchIndexerItem: | ||
+ | def __init__(self, | ||
+ | if bits: | ||
+ | self.bits=bits | ||
+ | else: | ||
+ | self.bits=[0 for i in range(780)] | ||
+ | if ayaId: self.setAyaId(ayaId) | ||
+ | | ||
+ | def setAyaId(self, | ||
+ | """ | ||
+ | ayaId [1-6236] | ||
+ | """ | ||
+ | i=ayaId-1 | ||
+ | self.bits[(i>> | ||
+ | | ||
+ | def __and__(self, | ||
+ | return searchIndexerItem(bits=[i and j for (i,j) in izip(self.bits, | ||
+ | | ||
+ | def toAyaIdList(self): | ||
+ | return filter(lambda k: k, | ||
+ | sum(map( lambda (i,j): | ||
+ | [ (j & 1) and (i<< | ||
+ | (j & 2) and (i<< | ||
+ | (j & 4) and (i<< | ||
+ | (j & 8) and (i<< | ||
+ | (j & 16) and (i<< | ||
+ | (j & 32) and (i<< | ||
+ | (j & 64) and (i<< | ||
+ | (j & 128) and (i<< | ||
+ | ] | ||
+ | , | ||
+ | |||
+ | class searchIndexer(dict): | ||
+ | def __init__(self, | ||
+ | dict.__init__(self) | ||
+ | self.normalize=normalize | ||
+ | self.maxWordLen=0 | ||
+ | | ||
+ | def save(self, fn): | ||
+ | s="" | ||
+ | m=(self.maxWordLen*2) | ||
+ | if os.path.exists(fn): | ||
+ | f=open(fn," | ||
+ | f.write(" | ||
+ | fmt=" | ||
+ | for w in self: | ||
+ | a=self[w].bits | ||
+ | s+=struct.pack(fmt, | ||
+ | f.write(zlib.compress(s, | ||
+ | f.close() | ||
+ | |||
+ | def load(self, fn): | ||
+ | f=open(fn," | ||
+ | m=int(f.readline().strip()) | ||
+ | fmt=" | ||
+ | size=struct.calcsize(fmt) | ||
+ | s=zlib.decompress(f.read()) | ||
+ | for i in range(0, | ||
+ | u=struct.unpack(fmt, | ||
+ | self[u[0].rstrip(' | ||
+ | |||
+ | def find(self, words): | ||
+ | if not words: return None | ||
+ | w=self.normalize(words[0]) | ||
+ | x=self.get(w, | ||
+ | if not x: return None | ||
+ | for w in words[1:]: | ||
+ | y=self.get(self.normalize(w), | ||
+ | if not y: return None | ||
+ | x&=y | ||
+ | return x.toAyaIdList() | ||
+ | | ||
+ | def addWord(self, | ||
+ | w=self.normalize(word) | ||
+ | self.maxWordLen=max(self.maxWordLen, | ||
+ | if self.has_key(w): | ||
+ | self[w].setAyaId(ayaId) | ||
+ | else: | ||
+ | self[w]=searchIndexerItem(ayaId) | ||
+ | |||
+ | </ | ||
+ | === العيوب والمزايا === | ||
+ | بعد عمل normalization كان هناك 14603 كلمة فريدة فإن كان لكل آية بت وحيث أنّه لدينا 6236 آية أي يلزمنا 780 بايت لكل كلمة + حجم الكلمة نفسها (وهذه حجمها أقصاه 12 حرفا أي 24 بايت) فتكون المحصّلة **11 ميغا بايت لحجم الفهرس** | ||
+ | |||
+ | قمت باستعمال zlib لضغط الفهرس فكان 270 كيلوبايت. | ||
+ | |||
+ | قمت بتحليل كائن البحث فكان حجمه 22 ميغابايت وقمت بمراقبة تحميل الفهرس في الذاكرة فكان يحتل 50 ميغابايت. | ||
+ | |||
+ | إلى جانب الحاجة لتحميل الفهرس كاملا في الذاكرة فإن هذه الطريقة لا توفّر طريقة مباشرة للبحث عن أجزاء من الكلمات. | ||
+ | |||
+ | سبب كبر الفهرس هو استعمال كل آية كوثيقة (وليس كل سورة كوثيقة) | ||
+ | |||
+ | ==== حقل البتات لكل سورة ==== | ||
+ | === العيوب والمزايا === | ||
+ | بما أنّ هناك 114 سورة هذا يعني أننا نحتاج 15 بايت لكل كلمة يعني 219 كيلوبايت مضافا لها مساحة لحفظ الكلمات. | ||
+ | |||
+ | لكن هذا يعني أنه بعد استعمال الفهرس سنعرف السور ثم علينا استعمال البحث التقليدي لمعرفة أي آية في السورة على وجه التعيين. | ||
+ | |||