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

تقدم محاولات بحثاً نصياً بتكاليف مستقلة عن حجم الوثيقة التي يتم البحث فيها، وبالتالي فهي مهمة للوثائق الكبيرة التي تتطلب أدوات تصحيح إملائي، وعدم حساسية لحالة الأحرف، وتخزين ثانوي تقريبي محدود. كانت عمليات البحث التقريبية، التي يختلف فيها نمط البحث عن الوثيقة بفضل k من الاستبدالات أو التبديلات أو الإدراجات أو الحذف، تتم حتى الآن فقط بتكاليف خطية تتناسب مع حجم الوثيقة. نقدم طريقة تعتمد على المحاولة بتكلفة مستقلة عن حجم الوثيقة. تظهر تجاربنا أن هذه الطريقة الجديدة تتفوق بشكل كبير على أقرب منافس لها عند k=0 و k=1، وهما على الأرجح الحالتان الأكثر أهمية. تبدأ التكلفة الخطية (في k) للطرق الأخرى في اللحاق بنا، بالنسبة لملفاتنا الصغيرة، فقط عند k=2. بالنسبة للملفات الأكبر، تشير الحجج المتعلقة بالتعقيد إلى أن المحاولات ستتجاوز الطرق الخطية لقيم أكبر من k. تتجمع الفهارس من اللواحق ولذلك فهي مضغوطة في التخزين. عندما لا تحتاج النصوص نفسها إلى التخزين، كما في أداة تصحيح الإملاء، نحصل حتى على تكلفة زائدة سلبية: 50% من الضغط. نناقش مجموعة متنوعة من التطبيقات والامتدادات، بما في ذلك أفضل تطابق (لأدوات تصحيح الإملاء)، وعدم حساسية حالة الأحرف، وتطابق التعبيرات العادية التقريبية المحدودة.