R - أطول فرعية شائعة

Question

هل يعرف أي شخص حزمة R التي تحل أطول مشكلة فرعية شائعة؟ أبحث عن شيء سريع يمكن أن يعمل على المتجهات.

Answer 1

تحقق من حزمة "rlibstree" على أوميغاهات: http://www.omegahat.org/rlibstree/.

هذا يستخدم http://www.icir.org/christian/libstree/.

Answer 2

يجب أن تنظر إلى LCS وظيفة qualV حزمة. يتم تنفيذه C ، وبالتالي فعال تمامًا.

Answer 3

السؤال هنا ليس واضحًا تمامًا بشأن التطبيق المقصود للحل لأطول مشكلة فرعية مشتركة. تطبيق شائع أواجهه هو مطابقة بين الأسماء في مجموعات البيانات المختلفة. ال stringdist الحزمة لها وظيفة مفيدة amatch() الذي أجده مناسبًا لهذه المهمة.

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

تفاصيل: amatch() يأخذ method الوسيطة التي تحددها lcs إذا كنت تريد المطابقة على أطول فرعية مشتركة. هناك العديد من الخيارات الأخرى لتقنيات مطابقة السلسلة المختلفة (على سبيل المثال مسافة Levenshtein). هناك أيضا إلزامي maxDist جدال. إذا كانت جميع الأوتار في table هي "مسافة" أكبر من سلسلة معينة في x, ، ومن بعد amatch() سيعود NA لهذا العنصر من الإخراج. يتم تعريف "المسافة" بشكل مختلف اعتمادًا على خوارزمية مطابقة السلسلة التي تختارها. بالنسبة إلى LCS ، فإنه (أكثر أو أقل) يعني فقط عدد الأحرف المختلفة (غير المتطابقة) الموجودة. انظر الوثائق للحصول على التفاصيل.

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

مثال التطبيق:

library(stringdist)

Names1 = c(
"SILVER EAGLE REFINING, INC. (SW)",
"ANTELOPE REFINING",
"ANTELOPE REFINING (DOUGLAS FACILITY)"
)

Names2 = c(
"Mobile Concrete, Inc.",
"Antelope Refining, LLC. ",
"Silver Eagle Refining Inc."
)

Match_Idx = amatch(tolower(Names1), tolower(Names2), method = 'lcs', maxDist = Inf)
Match_Idx
# [1] 3 2 2

Matches = data.frame(Names1, Names2[Match_Idx])
Matches

#                                 Names1          Names2.Match_Idx.
# 1     silver eagle refining, inc. (sw) silver eagle refining inc.
# 2                    antelope refining   antelope refining, llc. 
# 3 antelope refining (douglas facility)   antelope refining, llc. 

### Compare Matches:

Matches$Distance = stringdist(Matches$Names1, Matches$Match, method = 'lcs')

أيضا ، على عكس وظائف مثل LCS من qualV, ، لن يعتبر هذا مباريات "اللاحقة" التي تنطوي على تجاهل الشخصيات الوسيطة من أجل تكوين تطابق (كما نوقش هنا). على سبيل المثال ، انظر هذا:

Names1 = c(
"hello"
)

Names2 = c(
"hel123l5678o",
"hell"
)

Match_Idx = amatch(tolower(Names1), tolower(Names2), method = 'lcs', maxDist = Inf)

Matches = data.frame(Names1, Match = Names2[Match_Idx])
Matches

# 1  hello  hell

Answer 4

لا أعرف R ، لكنني اعتدت على تنفيذ خوارزمية Hirschberg التي هي سريعة ولا تستهلك مساحة كبيرة.

كما أتذكر أنه لا يسمى سوى 2 أو 3 وظائف قصيرة.

هنا رابط:http://wordaligned.org/articles/longest-common-subequence

لذلك لا تتردد في تنفيذها في R ، فهي تستحق الجهد لأنها خوارزمية مثيرة للاهتمام للغاية.