التشابه بين سلاسل الخط

Question

لدي عدد من المسارات المسجلة بواسطة نظام تحديد المواقع العالمي (GPS)، والتي يمكن وصفها بشكل أكثر رسمية بأنها عدد من سلاسل الخطوط.

الآن، قد تكون بعض المسارات المسجلة عبارة عن تسجيلات لنفس المسار، ولكن بسبب عدم الدقة في نظام تحديد المواقع العالمي (GPS)، وحقيقة أن التسجيلات تم إجراؤها في مناسبات منفصلة وأنه ربما تم تسجيلها وهي تسافر بسرعات مختلفة، فلن يتم ذلك تتطابق تمامًا، ولكنها لا تزال تبدو قريبة بدرجة كافية عندما يراها الإنسان على الخريطة لتحديد أنه في الواقع نفس المسار الذي تم تسجيله.

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

كيف يمكنك حساب التشابه، مع العلم أن الوسائل المتشابهة تمثل نفس المسار على الخريطة؟

يحرر: بالنسبة لأولئك الذين ليسوا متأكدين مما أتحدث عنه، يرجى إلقاء نظرة على هذا الرابط للحصول على تعريف لسلسلة السطر: http://msdn.microsoft.com/en-us/library/bb895372.aspx - أنا لا يسأل عن سلاسل الأحرف.

Answer 1

احسب ال مسافة فريشيه على كل زوج من المسارات.يمكن استخدام المسافة لقياس مدى تشابه مساراتك.

تنبيه الرياضيات: كان فريشيه رائداً في هذا المجال الفضاء المتري والتي هي ذات الصلة لمشكلتك.

Answer 2

أود إضافة مخزن مؤقت حول السطر الأول بناءً على الخطأ المحتمل المقدر، ثم تحديد ما إذا كان السطر الثاني يتناسب تمامًا مع المخزن المؤقت.

Answer 3

لتحديد "نفس المسار"، قم بإنشاء الحد الأدنى من مجموعة متجهات المسار المقيسة، واحسب إجمالي فروق الطاقة وقارن الإجمالي بمقياس الجودة.

1. تطبيع نقاط الطريق GPS على طول المسار الإجمالي،
2. السير على متجهات المسارات معًا، وإنشاء مجموعة جديدة من متجهات المسار لكل مسار بناءً على أقصر متجه في كل نقطة طريق،
3. حساب إجمالي فروق الطاقة بين نقاط النهاية لكل متجه في ترجيح المسارات الطبيعية لطول المتجه، و
4. مقارنة بمقياس الجودة.

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

قال بول تومبلين:أود إضافة مخزن مؤقت حول السطر الأول بناءً على الخطأ المحتمل المقدر ، ثم تحديد ما إذا كان السطر الثاني يناسب تمامًا داخل المخزن المؤقت.

يمكنك تعديل الخوارزمية عند مقارنة نقاط النهاية المتجهة التي تمت تسويتها.يمكنك تحديد ما إذا كان أي اختلاف في نقطة النهاية أعلى من حجم معين (تنفيذ فكرة المخزن المؤقت لبول) أو ربما، إذا كانت نقاط النهاية خارج "المخزن المؤقت"، استخدم هذه الحقيقة لتجاهل اختلاف نقطة النهاية، مما يسمح بإجراء مقارنة إهمال الرحلات الجانبية.

Answer 4

يمكنك المشي على طول كل نقطة (Pa) من LineString A وقياس المسافة من Pa إلى أقرب جزء من LineString B، مع حساب متوسط ​​كل من هذه المسافات.

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

هل تبدأ سلاسل الخطوط وتنتهي عند نقاط متشابهة، أم أنها ذات نطاقات مختلفة جدًا؟

Answer 5

إذا كنت تعتبر سلسلة سطر واحد عبارة عن سلسلة من النقاط [x,y] (أو نقاط [x,y,z])، فيمكنك حساب التشابه بين كل زوج من سلاسل الأسطر باستخدام نيدلمان وونش خوارزمية.كما هو موضح في مقالة ويكيبيديا المشار إليها، تتطلب خوارزمية Needleman-Wunsch "مصفوفة تشابه" تحدد المسافة بين زوج من النقاط.ومع ذلك، سيكون من السهل استخدام دالة بدلاً من المصفوفة.في حالتك يمكنك ببساطة استخدام 2D المسافة الإقليدية وظيفة (أو وظيفة إقليدية ثلاثية الأبعاد إذا كانت نقاطك لها ارتفاع) لتوفير المسافة بين كل زوج من النقاط.

Answer 6

أنا في الواقع أؤيد الشخص (آرون إف) الذي قال أنك قد تكون مهتمًا بمشكلة مسافة ليفنشتاين (واستشهد بها هذا).يبدو لي أن إجابته هي الأفضل حتى الآن.

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

في مشكلتك، يبدو أنك تتعامل مع الاختلافات بين سلاسل الأرقام، وتهتم بالأرقام.إذا قدمت المزيد من المعلومات، فقد أتمكن من توجيهك إلى الإصدار الصحيح من BLAST/FASTA/etc لأغراضك.على أية حال، قد تفكر في تكييف BLAST وFASTA ليناسب احتياجاتك.إنها بسيطة جدًا.

1: http://en.wikipedia.org/wiki/Levenshtein_distance, http://www.nist.gov/dads/HTML/Levenshtein.html