اختلافات

عرض الاختلافات بين النسخة المختارة و النسخة الحالية من الصفحة.

--- othman:search [2010/04/30 17:44] – تدقيق لغوي djilani
+++ 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://git.ojuba.org/cgit/othman/tree/?id=9722e57fe03c5ddfa0cc1a317516b190727787b0|رقم 9722e57fe03c5ddfa0cc1a317516b190727787b0]]
+وهذا [[http://git.ojuba.org/cgit/othman/tree/othman/core.py?id=9722e57fe03c5ddfa0cc1a317516b190727787b0|code.py]] منها
+<code python>
+normalize_tb={
+: 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,
+: 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): return s.translate(normalize_tb)
+class searchIndexerItem:
+  def __init__(self, ayaId=None, bits=None):
+    if bits:
+      self.bits=bits
+    else:
+      self.bits=[0 for i in range(780)]
+      if ayaId: self.setAyaId(ayaId)
+  def setAyaId(self, ayaId):
+    """
+    ayaId [1-6236]
+    """
+    i=ayaId-1
+    self.bits[(i>>3)]|=(1<<(i&7))
+  def __and__(self, y):
+    return searchIndexerItem(bits=[i and j for (i,j) in izip(self.bits, y.bits)])
+  def toAyaIdList(self):
+    return filter(lambda k: k,
+      sum(map( lambda (i,j):
+      [ (j & 1) and (i<<3)+1,
+        (j & 2) and (i<<3)+2,
+        (j & 4) and (i<<3)+3,
+        (j & 8) and (i<<3)+4,
+        (j & 16) and (i<<3)+5,
+        (j & 32) and (i<<3)+6,
+        (j & 64) and (i<<3)+7,
+        (j & 128) and (i<<3)+8,
+        ]
+      ,filter(lambda (ii,jj): jj,enumerate(self.bits))),[]))
+class searchIndexer(dict):
+  def __init__(self, normalize=normalize):
+    dict.__init__(self)
+    self.normalize=normalize
+    self.maxWordLen=0
+  def save(self, fn):
+    s=""
+    m=(self.maxWordLen*2)
+    if os.path.exists(fn): os.unlink(fn)
+    f=open(fn,"wb+")
+    f.write("%d\n" % m)
+    fmt="%ds780B" % m
+    for w in self:
+      a=self[w].bits
+      s+=struct.pack(fmt,w.encode('utf8'),*a)
+    f.write(zlib.compress(s,9))
+    f.close()
+  def load(self, fn):
+    f=open(fn,"rb")
+    m=int(f.readline().strip())
+    fmt="%ds780B" % m
+    size=struct.calcsize(fmt)
+    s=zlib.decompress(f.read())
+    for i in range(0,len(s),size):
+      u=struct.unpack(fmt,s[i:i+size])
+      self[u[0].rstrip('\0').decode('utf8')]=searchIndexerItem(bits=u[1:])
+  def find(self, words):
+    if not words: return None
+    w=self.normalize(words[0])
+    x=self.get(w,None)
+    if not x: return None
+    for w in words[1:]:
+      y=self.get(self.normalize(w),None)
+      if not y: return None
+      x&=y
+    return x.toAyaIdList()
+  def addWord(self, word, ayaId):
+    w=self.normalize(word)
+    self.maxWordLen=max(self.maxWordLen,len(w))
+    if self.has_key(w):
+      self[w].setAyaId(ayaId)
+    else:
+      self[w]=searchIndexerItem(ayaId)
+</code>
+=== العيوب والمزايا ===
+بعد عمل normalization كان هناك 14603 كلمة فريدة فإن كان لكل آية بت وحيث أنّه لدينا 6236 آية أي يلزمنا 780 بايت لكل كلمة + حجم الكلمة نفسها (وهذه حجمها أقصاه 12 حرفا أي 24 بايت) فتكون المحصّلة **11 ميغا بايت لحجم الفهرس**
+قمت باستعمال zlib لضغط الفهرس فكان 270 كيلوبايت.
+قمت بتحليل كائن البحث فكان حجمه 22 ميغابايت وقمت بمراقبة تحميل الفهرس في الذاكرة فكان يحتل 50 ميغابايت.
+إلى جانب الحاجة لتحميل الفهرس كاملا في الذاكرة فإن هذه الطريقة لا توفّر طريقة مباشرة للبحث عن أجزاء من الكلمات.
+سبب كبر الفهرس هو استعمال كل آية كوثيقة (وليس كل سورة كوثيقة)
+==== حقل البتات لكل سورة ====
+=== العيوب والمزايا ===
+بما أنّ هناك 114 سورة هذا يعني أننا نحتاج 15 بايت لكل كلمة يعني 219 كيلوبايت مضافا لها مساحة لحفظ الكلمات.
+لكن هذا يعني أنه بعد استعمال الفهرس سنعرف السور ثم علينا استعمال البحث التقليدي لمعرفة أي آية في السورة على وجه التعيين.