فاصله لونشتاین و شباهت متن در پایتون

معرفی

نوشتن متن یک خلاقیت است process که مبتنی است روی افکار و ایده هایی که به ذهن ما می رسد. روش نگارش متن نشان دهنده شخصیت ما است و همچنین بسیار تحت تأثیر حال و هوای ما، روشی که افکارمان را سازماندهی می کنیم، خود موضوع و افرادی که آن را به آنها خطاب می کنیم – خوانندگانمان.

در گذشته اتفاق می افتاد که دو یا چند نویسنده ایده مشابهی داشتند، آن را جداگانه نوشتند، به نام خود منتشر کردند و چیزی را خلق کردند که بسیار شبیه بود. قبل از انتشارات الکترونیکی، ایده های آنها مدتی طول کشید تا به جریان افتاد و بنابراین منجر به درگیری در مورد مخترع واقعی و اینکه چه کسی باید برای آن مورد تقدیر قرار گیرد، شد.

امروزه، هر مقاله بلافاصله به صورت آنلاین در قالب دیجیتال در دسترس است. مقالات آنلاین به درستی نمایه می شوند و به اسناد دیگر پیوند داده می شوند که یافتن سریع آنها را آسان می کند. از یک طرف این روش کار تبادل نظر و همچنین تحقیق در مورد یک موضوع را ساده می کند روی از سوی دیگر دسترسی پذیری درهایی را برای کپی و پیست کردن کارهای دیگران بدون اجازه یا تایید آنها باز می کند که به آن سرقت ادبی می گویند.

در این مرحله روش هایی وارد عمل می شوند که به شباهت متون مختلف می پردازند. ایده اصلی پشت این موضوع این است که بتوانیم به سؤالات پاسخ دهیم اگر دو متن (یا مجموعه داده ها به طور کلی) کاملاً یا حداقل تا حدی مشابه هستند، آیا از نظر موضوعی مشابه به یکدیگر مرتبط هستند و تعداد ویرایش ها باید انجام شود. برای تبدیل یک متن به متن دیگر انجام می شود.

به عنوان مثال، این فناوری توسط سیستم‌های بازیابی اطلاعات، موتورهای جستجو، سیستم‌های نمایه‌سازی خودکار، خلاصه‌کننده‌های متن، سیستم‌های دسته‌بندی، بررسی‌کننده سرقت ادبی، تشخیص گفتار، سیستم‌های رتبه‌بندی، تجزیه و تحلیل DNA و الگوریتم‌های پروفایل (برنامه‌های IR/AI برای پیوند خودکار داده‌ها) استفاده می‌شود. بین مردم و آنچه انجام می دهند).

روش های جستجو و مقایسه

همه ما با جستجوی متن برای یک کلمه یا دنباله کاراکتر مشخص (الگو) آشنا هستیم. هدف یافتن رخداد دقیق (تطابق) یا یافتن یک تطابق دقیق با استفاده از کاراکترهایی با معنای خاص است، برای مثال توسط عبارات با قاعده یا توسط منطق فازی. بیشتر، دنباله ای از شخصیت ها است که شبیه به دیگری است.

علاوه بر این، شباهت را می توان با روش صدای کلمات اندازه گیری کرد — آیا آنها شبیه به نظر می آیند اما به روشی متفاوت نوشته می شوند؟ ترجمه از یک الفبا به الفبای دیگر اغلب بسته به یک نتیجه بیشتر می دهد روی زبان، بنابراین برای پیدا کردن خویشاوندان بر اساس روی املای مختلف نام خانوادگی و نام آنها الگوریتم Soundex ایجاد شد و هنوز هم یکی از محبوب ترین و گسترده ترین الگوریتم های امروزی است.

آخرین اما نه کم اهمیت، چند تغییر (ویرایش) برای رسیدن از یک کلمه به کلمه دیگر لازم است؟ هرچه ویرایش های کمتری انجام شود، سطح شباهت بالاتر است. این دسته از مقایسه شامل فاصله لونشتاین که تمرکز خواهیم کرد روی با جزئیات بیشتر در زیر

میز 1 مجموعه‌ای از روش‌های جستجو و مقایسه داده‌های متنی را پوشش می‌دهد. ستون سمت راست جدول شامل مجموعه ای از ماژول های پایتون مربوطه برای دستیابی به این وظایف است.

میز 1

فاصله لونشتاین

این روش در سال 1965 توسط ریاضیدان روسی ولادیمیر لونشتاین (1935-2017) ابداع شد. مقدار فاصله حداقل تعداد حذف، درج یا جایگزینی مورد نیاز برای تبدیل یک رشته (منبع) به رشته دیگر (هدف) را توصیف می کند. بر خلاف فاصله همینگ، فاصله لونشتاین کار می کند روی رشته هایی با طول نابرابر

هر چه فاصله لونشتاین بیشتر باشد، تفاوت بین سیم ها بیشتر می شود. به عنوان مثال، از “تست” تا “تست” فاصله Levenshtein 0 است زیرا هر دو رشته منبع و هدف یکسان هستند. هیچ تغییری لازم نیست. در مقابل، از “تست” تا “تیم” فاصله لونشتاین 2 است – دو تعویض باید انجام شود تا “تست” به “تیم” تبدیل شود.

در اینجا یک ویدیو عالی است که روش عملکرد الگوریتم را توضیح می دهد:

https://www.youtube.com/watch؟v=We3YDTzNXEk

پیاده سازی فاصله لونشتاین در پایتون

برای پایتون، چند پیاده‌سازی مختلف به صورت آنلاین (9،10) و همچنین از بسته‌های مختلف پایتون (جدول بالا را ببینید) وجود دارد. این شامل نسخه های زیر است برنامه نویسی پویا مفهوم و همچنین نسخه های برداری شده. نسخه ای که در اینجا نشان می دهیم یک نسخه تکراری است که از بسته NumPy و یک ماتریس واحد برای انجام محاسبات استفاده می کند. به عنوان مثال می خواهیم فاصله ویرایش بین “تست” و “متن” را دریابیم.

با یک ماتریس خالی شروع می شود که اندازه طول رشته ها را دارد. هر دو سطر و ستون اول، که از صفر شروع می شوند، به طور فزاینده ای ایندکس می شوند:

         t   e   s   t
  (( 0.  1.  2.  3.  4.)
 t ( 1.  0.  0.  0.  0.)
 e ( 2.  0.  0.  0.  0.)
 x ( 3.  0.  0.  0.  0.)
 t ( 4.  0.  0.  0.  0.))

در مرحله بعد، دو حلقه دنبال می‌شوند تا رشته‌ها را حرف به حرف با هم مقایسه کنند – از نظر ردیف و ستون. اگر دو حرف برابر باشند، مقدار جدید در موقعیت (x, y) حداقل بین مقدار موقعیت است (x-1, y) + 1، موقعیت (x-1, y-1)، و موقعیت (x, y-1) + 1.

(+0.) (+1.)
(+1.) (   )

در غیر این صورت، حداقل بین مقدار موقعیت است (x-1, y) + 1، موقعیت (x-1, y-1) + 1، و موقعیت (x, y-1) + 1. باز هم، این را می توان به عنوان یک ماتریس فرعی دو به دو تجسم کرد که در آن شما مقدار گمشده را در موقعیت پایین سمت راست به صورت زیر محاسبه می کنید:

(+1.) (+1.)
(+1.) (   )

توجه داشته باشید که در صورت متفاوت بودن دو کاراکتر سه نوع تغییر وجود دارد – درج، حذف و جایگزین. در نهایت، ماتریس به صورت زیر است:

         t   e   s   t
  (( 0.  1.  2.  3.  4.)
 t ( 1.  0.  1.  2.  3.)
 e ( 2.  1.  0.  1.  2.)
 x ( 3.  2.  1.  1.  2.)
 t ( 4.  3.  2.  1.  1.))

فاصله ویرایش مقدار در موقعیت (4، 4) – در گوشه پایین سمت راست – است که در واقع 1 است. توجه داشته باشید که این پیاده سازی در O(N*M) زمان برای N و M طول دو رشته سایر پیاده سازی ها ممکن است در زمان کمتری اجرا شوند، اما درک آنها جاه طلبانه تر است.

در اینجا کد مربوط به الگوریتم فاصله لونشتاین است که من توضیح دادم:

import numpy as np

def levenshtein(seq1, seq2):
    size_x = len(seq1) + 1
    size_y = len(seq2) + 1
    matrix = np.zeros ((size_x, size_y))
    for x in xrange(size_x):
        matrix (x, 0) = x
    for y in xrange(size_y):
        matrix (0, y) = y

    for x in xrange(1, size_x):
        for y in xrange(1, size_y):
            if seq1(x-1) == seq2(y-1):
                matrix (x,y) = min(
                    matrix(x-1, y) + 1,
                    matrix(x-1, y-1),
                    matrix(x, y-1) + 1
                )
            else:
                matrix (x,y) = min(
                    matrix(x-1,y) + 1,
                    matrix(x-1,y-1) + 1,
                    matrix(x,y-1) + 1
                )
    print (matrix)
    return (matrix(size_x - 1, size_y - 1))

منابع

سپاسگزاریها

نویسنده مایل است تشکر کند
اکسل بکرتمندی نیومایر، جرولد روپرشت و زولکا هاتیتونگه برای حمایت آنها در هنگام تهیه مقاله.