أدوات المستخدم

أدوات الموقع


othman:search

اختلافات

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

رابط إلى هذه المقارنة

جانبي المراجعة السابقة المراجعة السابقة
othman:search [2010/04/30 14:44]
djilani تدقيق لغوي
othman:search [2015/04/23 00:21] (حالي)
سطر 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={
 +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)
 +
 +</​code>​
 +=== العيوب والمزايا ===
 +بعد عمل normalization كان هناك 14603 كلمة فريدة فإن كان لكل آية بت وحيث أنّه لدينا 6236 آية أي يلزمنا 780 بايت لكل كلمة + حجم الكلمة نفسها (وهذه حجمها أقصاه 12 حرفا أي 24 بايت) فتكون المحصّلة **11 ميغا بايت لحجم الفهرس**
 +
 +قمت باستعمال zlib لضغط الفهرس فكان 270 كيلوبايت.
 +
 +قمت بتحليل كائن البحث فكان حجمه 22 ميغابايت وقمت بمراقبة تحميل الفهرس في الذاكرة فكان يحتل 50 ميغابايت.
 +
 +إلى جانب الحاجة لتحميل الفهرس كاملا في الذاكرة فإن هذه الطريقة لا توفّر طريقة مباشرة للبحث عن أجزاء من الكلمات.
 +
 +سبب كبر الفهرس هو استعمال كل آية كوثيقة (وليس كل سورة كوثيقة)
 +
 +==== حقل البتات لكل سورة ====
 +=== العيوب والمزايا ===
 +بما أنّ هناك 114 سورة هذا يعني أننا نحتاج 15 بايت لكل كلمة يعني 219 كيلوبايت مضافا لها مساحة لحفظ الكلمات.
 +
 +لكن هذا يعني أنه بعد استعمال الفهرس سنعرف السور ثم علينا استعمال البحث التقليدي لمعرفة أي آية في السورة على وجه التعيين.
 +