othman:search

محرك البحث في النّص القرآني

يُفترض أن يستخدم محرّك البحث مجموعة من الخوارزميات المحسّنة المصمّمة خصيصاً للنّص القرآني بحيث نوفّر الوقت والحجم (أي حجم الفهرس).

والمقصود بالبحث هنا هو البحث في النّص القرآني بالرّسم الإملائي المضبوط بقراءة حفص عن عاصم.

طرق التحسين العامة

  • لا نحتاج لإدارة عمليات الإضافة والحذف فهذه العملية تتم مرة واحدة عند بناء الحزمة لثبات النص.
  • لا يهتم من يبحث في النّص القرآني عن ترتيب (rank)للنتائج بل يريدها حسب مكان ورودها في المصحف لأن النّاس تتذكّر النّص القرآني حرفيا.
  • ترقيم الآيات واحدة بعد الأخرى يعني الآية التاسعة (رقم 8) هي الآية الثانية من سورة البقرة (نعلم ذلك بعمل bisect للعدد التراكمي للآيات في السور: يعني: 7 ثم 7+286 ثم 7+286+200 وهكذا)
  • عمل bit field مكون من 6236 بت كل واحد يمثل آية (أي 780 بايت)
  • تجذيع الكلمات ولكل كلمة نعمل كائن من النّوع السابق يمثّل أماكن ورودها ب 1 في البت المقابل للآية.
  • إن أردنا البحث عن العبارات (كلمات متتابعة) وليس الكلمات يمكن:
    1. استخراج نتائج البحث عن الكلمات ثم عمل بحث غير مفهرس فيها
    2. أو يمكن الاحتفاظ ب term vector مقابل كل كلمة
  • أكبر عدد من الكلمات في الآية 129 وهو في آية الدَّين في سورة البقرة وهذا يعني أن بايت واحد يكفي لتمثيل الكلمة في الآية.
  • يستحيل أن تتكرّر الكلمة أكثر من 129 مرة في الآية الواحدة (للسبب السابق) أي أن بايت واحد يكفي لبيان عدد مرّات ورود الكلمة في الآية
  • يتكوّن term vector من:
    • تكرار الكلمة في كل آية تحتوي الكلمة مثلا 1 ثم 2 ثم 1 ثم 1 تعني أن الكلمة وردت 5 مرات.
    • قائمة بأرقام الكلمات وفي المثال نحتاج 5 أرقام.

طرق التفيذ

حاولت مقاومة استعمال sqlite حيث ظننت أن عمل ملف باستعمال struct سيفيد إلاّ أنّي في النّهاية استعملت قائمة بأرقام الآيات محفوظة في sqlite

قائمة أرقام الآيات

من التبذير تخصيص 1 بت لكل آية في كل كلمة حيث أن كلمة مثل “مجراها” غير موجودة إلا في آية واحدة حيث ستكون كل البتات أصفارا إلاّ واحدة منها.

فإن استخدمنا الكلمة ثمّ : ثمّ رقم الآية فسيكون حجم الملف نصف ميغابايت وإن استعملنا 16-بت لتمثيل رقم الآية سيكون حجم الفهرس 300 كيلوبايت.

وبعد عملها على شكل sqlite كان حجم الملف تقريبا 750 كيلوبابت لكنّنا في هذه الحالة كسبنا البحث عن جزء من الكلمة.

لتسريع عمليات و/أو استخدمت set في بايثون.

حقل البتات لكل آية

الكود

تمّ تجربة ذلك في إصدارة قديمة ذات رقم 9722e57fe03c5ddfa0cc1a317516b190727787b0 وهذا code.py منها

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): 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)

العيوب والمزايا

بعد عمل normalization كان هناك 14603 كلمة فريدة فإن كان لكل آية بت وحيث أنّه لدينا 6236 آية أي يلزمنا 780 بايت لكل كلمة + حجم الكلمة نفسها (وهذه حجمها أقصاه 12 حرفا أي 24 بايت) فتكون المحصّلة 11 ميغا بايت لحجم الفهرس

قمت باستعمال zlib لضغط الفهرس فكان 270 كيلوبايت.

قمت بتحليل كائن البحث فكان حجمه 22 ميغابايت وقمت بمراقبة تحميل الفهرس في الذاكرة فكان يحتل 50 ميغابايت.

إلى جانب الحاجة لتحميل الفهرس كاملا في الذاكرة فإن هذه الطريقة لا توفّر طريقة مباشرة للبحث عن أجزاء من الكلمات.

سبب كبر الفهرس هو استعمال كل آية كوثيقة (وليس كل سورة كوثيقة)

حقل البتات لكل سورة

العيوب والمزايا

بما أنّ هناك 114 سورة هذا يعني أننا نحتاج 15 بايت لكل كلمة يعني 219 كيلوبايت مضافا لها مساحة لحفظ الكلمات.

لكن هذا يعني أنه بعد استعمال الفهرس سنعرف السور ثم علينا استعمال البحث التقليدي لمعرفة أي آية في السورة على وجه التعيين.

نقاش

احمد عبدالمنعم, 2011/11/05 09:30

جزاك اللة كل خير ونفع بك وجعلة صدقة جارية لك

Ciho, 2012/07/30 19:05

Your answer lifts the intelligence of the dbetae.

أدخل تعليقك:
 
آخر تعديل:: 23 نيسان 2015 الساعة 00:21 (تحرير خارجي)