خوارزمية للعثور على أقرب سلسلة باستخدام نفس الأحرف

Question

بالنظر إلى قائمة L من سلاسل الأحرف n، وسلسلة الأحرف المدخلة S، ما هي الطريقة الفعالة للعثور على سلسلة الأحرف في L التي تحتوي على معظم الأحرف الموجودة في S؟نريد العثور على السلسلة في L التي تتكون بشكل وثيق من الحروف الموجودة في S.

الإجابة الواضحة هي تكرار جميع السلاسل n والتحقق لمعرفة عدد الأحرف الموجودة في السلسلة الحالية الموجودة في S.ومع ذلك، سيتم تشغيل هذه الخوارزمية بشكل متكرر، وسيتم تخزين القائمة L من السلسلة n في قاعدة بيانات...تتطلب الحلقة اليدوية عبر جميع السلاسل n شيئًا مثل big-Oh لـ n*m^2، حيث n هو عدد السلاسل في L، وm هو الحد الأقصى لطول أي سلسلة في L، بالإضافة إلى الحد الأقصى لطول S ...في هذه الحالة m هو في الواقع ثابت قدره 150.

هل هناك طريقة أفضل من مجرد حلقة بسيطة؟هل هناك بنية بيانات يمكنني تحميل سلاسل n فيها مما يمنحني قدرة بحث سريعة؟هل هناك خوارزمية تستخدم البيانات الوصفية المحسوبة مسبقًا حول كل سلسلة من السلاسل n والتي من شأنها أن تؤدي أداءً أفضل من الحلقة؟

أعلم أن هناك الكثير من المهووسين بالخوارزميات.لذا يرجى المساعدة!

شكرًا!

Answer 1

إذا كنت بعد السلاسل الفرعية، أ حاول أو قد تكون محاولة باتريكا نقطة انطلاق جيدة.

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

               ABCDEFGHIJKLMNOPQRSTUVWXYZ
Hello World => ...11..1...3..2..1....1...

وهذا سوف يقلل من التكاليف ل O(26 * m + n) بالإضافة إلى المعالجة المسبقة مرة واحدة إذا كنت تفكر فقط في الحروف اللاتينية غير الحساسة لحالة الأحرف.

إذا كانت m ثابتة، فيمكنك تفسير الرسم البياني على أنه متجه ذو 26 بُعدًا على كرة وحدة ذات 26 بُعدًا عن طريق تطبيعه.ثم يمكنك فقط حساب المنتج نقطة لمتجهين ينتج عنهما جيب تمام الزاوية بين المتجهين، ويجب أن تكون هذه القيمة متناسبة مع تشابه السلاسل.

على افتراض m = 3, ، الأبجدية A = { 'U', 'V', 'W' } من الحجم الثالث فقط، وقائمة السلاسل التالية.

L = { "UUU", "UVW", "WUU" }

الرسوم البيانية هي التالية.

H = { (3, 0, 0), (1, 1, 1), (2, 0, 1) }

رسم بياني h = (x, y, z) يتم تطبيع ل h' = (x/r, y/r, z/r) مع r القاعدة الإقليدية للرسم البياني h - إنه r = sqrt(x² + y² + z²).

H' = { (1.000, 0.000, 0.000), (0.577, 0.577, 0.577), (0.894, 0.000, 0.447) }

المدخل S = "VVW" لديه الرسم البياني hs = (0, 2, 1) والرسم البياني تطبيع hs' = (0.000, 0.894, 0.447).

الآن يمكننا حساب التشابه بين الرسمين البيانيين h1 = (a, b, c) و h2 = (x, y, z) كالمسافة الإقليدية لكلا الرسمين البيانيين.

d(h1, h2) = sqrt((a - x)² + (b - y)² + (c - z)²)

على سبيل المثال نحصل عليه.

d((3, 0, 0), (0, 2, 1)) = 3.742
d((1, 1, 1), (0, 2, 1)) = 1.414
d((2, 0, 1), (0, 2, 1)) = 2.828

ومن ثم فإن "UVW" هو الأقرب إلى "VVW" (تشير الأرقام الأصغر إلى تشابه أعلى).

باستخدام الرسوم البيانية تطبيع h1' = (a', b', c') و h2' = (x', y', z') يمكننا حساب المسافة كمنتج نقطي لكلا الرسمين البيانيين.

d'(h1', h2') = a'x' + b'y' + c'z'

على سبيل المثال نحصل عليه.

d'((1.000, 0.000, 0.000), (0.000, 0.894, 0.447)) = 0.000
d'((0.577, 0.577, 0.577), (0.000, 0.894, 0.447)) = 0.774
d'((0.894, 0.000, 0.447), (0.000, 0.894, 0.447)) = 0.200

مرة أخرى، تم تحديد "UVW" ليكون الأقرب إلى "VVW" (تشير الأرقام الأكبر إلى تشابه أعلى).

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

Answer 2

ويبدو وكأنه كنت في حاجة الى TRIE . تستخدم محاولات للبحث عن كلمات مماثلة للطريقة التي سوف يعمل المدقق الإملائي. إذا كان الأمر كذلك سلسلة S ديه الأحرف في نفس الترتيب كما سلاسل في L ثم هذا قد عمل لك.

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

Answer 3

ما تريده هو BK- شجرة . انها قليلا unintuitive، ولكن باردة جدا - ويجعل من الممكن للبحث عن العناصر داخل levenshtein (تحرير) عتبة المسافة في O (سجل ن) وقت

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

Answer 4

وأعتقد أن ما كنت تبحث عن ويمكن العثور عليها هنا: <لأ href = "http://publications.drdo.gov.in/gsdl/collect/dbit/index/assoc/HASH5495.dir/dbit2406003.pdf "يختلط =" نوفولو noreferrer "> منطق ضبابي وبناء البحث وتقنيات

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

i.e:

L I N E A R T R N A S F O R M
L I N A E R T R A N S F O R M
L E N E A R T R A N S F R M

Answer 5

ويبدو لي أن ترتيب الأحرف ليست مهمة في مشكلتك، ولكن كنت تبحث عن "شبه الجناس" كلمة S.

إذا كان الأمر كذلك، ثم يمكنك تمثيل كل كلمة في مجموعة L باعتبارها مجموعة من 26 الأعداد الصحيحة (على افتراض الأبجدية الخاصة بك لديها 26 حرفا). يمكنك تمثيل S بالمثل باعتبارها مجموعة من 26 الأعداد الصحيحة. الآن لإيجاد أفضل مباراة لك فقط تشغيل مرة واحدة من خلال مجموعة L وحساب مسافة متري بين S-ناقلات والحالي L-ناقلات، ولكن تريد لتحديد المسافة المترية (على سبيل المثال الإقليدية / مبلغ من المربعات أو مانهاتن / مجموع الفروق المطلقة). هذا هو O (ن) خوارزمية لناقلات لها أطوال مستمرة.

Answer 6

وهنا هي وظيفة T-SQL التي تم عمل عظيم بالنسبة لي، ويعطي لك المسافة تحرير:

مثال:

  SELECT TOP 1 [StringValue] , edit_distance([StringValue, 'Input Value')
    FROM [SomeTable]
ORDER BY edit_distance([StringValue, 'Input Value')

وظيفة:

CREATE FUNCTION edit_distance(@s1 nvarchar(3999), @s2 nvarchar(3999))
RETURNS int
AS
BEGIN
  DECLARE @s1_len int, @s2_len int, @i int, @j int, @s1_char nchar, @c int, @c_temp int,
    @cv0 varbinary(8000), @cv1 varbinary(8000)
  SELECT @s1_len = LEN(@s1), @s2_len = LEN(@s2), @cv1 = 0x0000, @j = 1, @i = 1, @c = 0
  WHILE @j <= @s2_len
    SELECT @cv1 = @cv1 + CAST(@j AS binary(2)), @j = @j + 1
  WHILE @i <= @s1_len
  BEGIN
    SELECT @s1_char = SUBSTRING(@s1, @i, 1), @c = @i, @cv0 = CAST(@i AS binary(2)), @j = 1
    WHILE @j <= @s2_len
    BEGIN
      SET @c = @c + 1
      SET @c_temp = CAST(SUBSTRING(@cv1, @j+@j-1, 2) AS int) +
        CASE WHEN @s1_char = SUBSTRING(@s2, @j, 1) THEN 0 ELSE 1 END
      IF @c > @c_temp SET @c = @c_temp
      SET @c_temp = CAST(SUBSTRING(@cv1, @j+@j+1, 2) AS int)+1
      IF @c > @c_temp SET @c = @c_temp
      SELECT @cv0 = @cv0 + CAST(@c AS binary(2)), @j = @j + 1
    END
    SELECT @cv1 = @cv0, @i = @i + 1
  END
  RETURN @c
END