سلسلة تقريبية مطابقة مع مصفوفة ارتباك الحروف؟

Question

أحاول تصميم معرف التعرف الصوتي الذي يتعين على عزل حالات الكلمات (سلاسل الهواتف) من مجموعة طويلة من الهواتف التي لا تحتوي على فجوات بين كل كلمة. قد يكون دفق الهواتف غير معترف به بشكل سيء ، مع بدائل الحروف/الإدراج/الحذف ، لذلك سيتعين علي القيام بمطابقة سلسلة تقريبية.

ومع ذلك ، أريد أن تكون المطابقة ذات دوافع صوتيًا ، على سبيل المثال "M" و "N" متشابهة صوتيًا ، وبالتالي فإن تكلفة استبدال "M" لـ "n" يجب أن تكون صغيرة ، مقارنةً بـ "M" و "K" ". لذا ، إذا كنت أبحث عن [Mein] "Main" ، فسيتطابق مع تسلسل الحروف [Meim] "Maim" مع ، على سبيل المثال ، تكلفة 0.1 ، في حين أنه سيتطابق مع تسلسل الرسالة [Meik] "Make" مع ، على سبيل المثال ، على سبيل المثال ، تكلفة 0.7. وبالمثل ، هناك تكاليف مختلفة لإدخال أو حذف كل حرف. يمكنني توفير مصفوفة ارتباك ، لكل زوج أحرف (x ، y) ، يعطي تكلفة استبدال x مع y ، حيث x و y هي أي حرف أو سلسلة فارغة.

أعلم أن هناك أدوات متوفرة تتم مطابقة تقريبية مثل agrep, ، ولكن بقدر ما أستطيع أن أقول ، فإنهم لا يأخذون مصفوفة الارتباك كمدخلات. أي تكلفة أي الإدراج/الاستبدال/الحذف = 1. سؤالي هو ، هل هناك أي أدوات مفتوحة المصدر متوفرة بالفعل يمكنها القيام بالمطابقة التقريبية مع مصفوفات الارتباك ، وإذا لم يكن الأمر كذلك ، فما هي الخوارزمية الجيدة التي يمكنني تنفيذها لإنجاز هذا؟

تحرير: فقط لكي أكون واضحًا ، أحاول عزل مثيلات تقريبية لكلمة مثل [mein] من سلسلة أطول ، على سبيل المثال [aiammeinlimeiking ...]. من الناحية المثالية ، يجب أن تقوم الخوارزمية/الأداة بالإبلاغ عن مثيلات مثل [Mein] بتكلفة 0.0 (مطابقة دقيقة) ، [Meik] بتكلفة 0.7 (بالقرب من المطابقة) ، إلخ ، لجميع تطابقات السلسلة التقريبية بتكلفة أقل من عتبة معينة.

Answer 1

لست على دراية بأي معرفات صوتية تستخدم مصفوفات الارتباك. أنا أعلم عن Soundex, ، و تصنيف المباراة.

أعتقد أن خوارزمية جار جار قد يكون مفيدًا لنوع التقريب الذي تهتم به.

Answer 2

بيتر كليويج البساط/L04 (من أجل الجدلية الحسابية) يتضمن تنفيذ مسافة Levenshtein والذي يتيح لك تحديد تكاليف الإدراج غير الموحد والحذف والاستبدال.