مقياس السلسلة

📅 آخر تحديث: ٢٢ يوليو ٢٠٢٦
✍️ نُشر في: ٢٢ يوليو ٢٠٢٦
📷 يحتوي على 3 صور
الموسوعة الحرة

في الرياضيات وعلوم الحاسوب ، يُعرف مقياس السلسلة (أو مقياس تشابه السلاسل أو دالة مسافة السلاسل ) بأنه مقياس يقيس المسافة (التشابه العكسي) بين سلسلتين نصيتين لأغراض المطابقة التقريبية أو المقارنة، وكذلك في البحث التقريبي عن السلاسل . ومن متطلبات مقياس السلسلة (على عكس مطابقة السلاسل مثلاً ) تحقق متباينة المثلث . فعلى سبيل المثال، يمكن اعتبار السلسلتين "Sam" و"Samuel" متقاربتين. [ 1 ] ويُقدم مقياس السلسلة قيمة عددية تُشير إلى مستوى المسافة الخاص بالخوارزمية.

يُعدّ مقياس ليفنشتاين (المعروف أيضًا بمسافة التحرير) من أكثر مقاييس السلاسل النصية شيوعًا. [ 2 ] وهو مقياس بسيط يُجرى على سلسلتين نصيتين، ويُعيد قيمة عددية تُعادل عدد عمليات الاستبدال والحذف اللازمة لتحويل إحداهما إلى الأخرى. وقد توسّعت مقاييس السلاسل النصية البسيطة، مثل مسافة ليفنشتاين، لتشمل طرقًا صوتية، ورموزًا ، وقواعد نحوية، وأساليب إحصائية تعتمد على الأحرف.

تُستخدم مقاييس السلاسل بشكل كبير في تكامل المعلومات ، وتُستخدم حاليًا في مجالات تشمل كشف الاحتيال ، وتحليل بصمات الأصابع ، وكشف الانتحال ، ودمج الأنطولوجيا ، وتحليل الحمض النووي ، وتحليل الحمض النووي الريبي، وتحليل الصور ، والتعلم الآلي القائم على الأدلة ، وإزالة البيانات المكررة من قواعد البيانات ، واستخراج البيانات ، والبحث التدريجي ، وتكامل البيانات ، وكشف البرامج الضارة ، [ 3 ] وتكامل المعرفة الدلالية .

قائمة مقاييس السلاسل النصية

توجد أيضاً دوال تقيس الاختلاف بين السلاسل النصية، لكنها لا تحقق بالضرورة متباينة المثلث، وبالتالي فهي ليست مقاييس بالمعنى الرياضي. ومن أمثلة هذه الدوال مسافة جارو-وينكلر .

أمثلة مختارة لمقاييس السلاسل

اسموصفمثال
مسافة هامينغفقط للسلاسل ذات الطول نفسه. عدد الأحرف المتغيرة." ka rol in " و " ka thr in " تساوي 3.
مسافة ليفنشتاين ومسافة داميراو-ليفنشتاينتعميم مسافة هامينغ التي تسمح بأطوال مختلفة للأوتار، ومع داميراو (للنقلات الموسيقية).المسافة بين kitt e n و sitt ing هي 3 .
  1. k itten → s itten (استبدال "s" بـ "k")
  2. sitt e n → sitt i n (استبدال "i" بـ "e")
  3. sittin → sittin g (إضافة حرف "g" في النهاية).
مسافة جارو-وينكلرJaroWinklerDist("MARTHA","MARHTA") =
دج=13(م|s1|+م|s2|+م-تم)=13(66+66+6-226)=0.944{\displaystyle d_{j}={\frac {1}{3}}\left({\frac {m}{|s_{1}|}}+{\frac {m}{|s_{2}|}}+{\frac {mt}{m}}\right)={\frac {1}{3}}\left({\frac {6}{6}}+{\frac {6}{6}}+{\frac {6-{\frac {2}{2}}}{6}}\right)=0.944}
  • م{\displaystyle m}هو عدد الأحرف المتطابقة ؛
  • ت{\displaystyle t}يمثل نصف عدد عمليات النقل ( "MARTHA"[3]!=H, "MARHTA"[3]!=T).
أكثر الأحرف التي تبدأ بحرف k شيوعًاMostFreqKeySimilarity(' r e s e a r ch', 'seeking ' , 2) = 2

مراجع

  1. ↑ لو، جيا هينغ؛ وآخرون  (2013). "مقاييس تشابه السلاسل النصية والربط بالمترادفات" . وقائع مؤتمر ACM SIGMOD الدولي لإدارة البيانات لعام 2013. الصفحات 373-384 . doi : 10.1145/2463676.2465313 . ISBN  9781450320375. S2CID 2091942 . 
  2. ↑ نافارو، غونزالو (2001). "جولة إرشادية لتقريب مطابقة السلاسل النصية". مجلة ACM Computing Surveys . 33 (1): 31–88 . doi : 10.1145/375360.375365 . hdl : 10533/172862 . S2CID 207551224 . 
  3. ↑ شلومي دوليف ؛ محمد غنايم؛ ألكسندر بينون؛ سيرجي فرينكل؛ يالي، إس. صن (2017). "العلاقة بين معامل جاكارد ومسافة التحرير في تجميع البرامج الضارة وتحديدها عبر الإنترنت". المؤتمر الدولي السادس عشر لمعهد مهندسي الكهرباء والإلكترونيات حول الحوسبة الشبكية وتطبيقاتها : 369-373 .
  4. 1 2 3 4 5 مقاييس سام للسلاسل - اللغويات الحاسوبية وعلم الصوتيات
  5. ↑ راسل، ديفيد جيه، وآخرون. "مقياس المسافة القائم على القواعد النحوية يُمكّن من التجميع السريع والدقيق لمجموعات كبيرة من تسلسلات 16S." BMC bioinformatics 11.1 (2010): 1-14.
  6. ↑ كوهين، ويليام؛ رافيكومار، براديب؛ فينبرغ، ستيفن (2003-08-01). "مقارنة مقاييس مسافة السلسلة لمهام مطابقة الأسماء" : 73-78 .{{cite journal}}يتطلب الاستشهاد بالمجلة ( مساعدة )|journal=