شباهت آوایی کلمات: رویکرد برداری در پایتون

در مقاله قبلی مقدمه ای از الگوریتم های آوایی به شما ارائه دادم و تنوع آنها را نشان دادم. با جزئیات بیشتر نگاهی به فاصله ویرایش داشتیم که به آن نیز معروف است فاصله لونشتاین. این الگوریتم به منظور محاسبه تعداد جانشینی حروف برای رسیدن از یک کلمه به کلمه دیگر توسعه یافته است.

همانطور که قبلاً در مقاله قبلی اشاره کرده اید، روش های مختلفی برای محاسبه صدای کلمه ای مانند Soundex، Metaphone و Match Rating codex وجود دارد. برخی از آنها شایع تر از دیگران هستند. به عنوان مثال، پیاده سازی Soundex بخشی از هر زبان برنامه نویسی و همچنین سیستم های مدیریت پایگاه داده (DBMS) مانند Oracle، MySQL و PostgreSQL است. در مقابل، Metaphone و Match Rating Codex به ندرت مورد استفاده قرار می گیرند و در بیشتر موارد نیاز به نصب کتابخانه های نرم افزاری اضافی دارند. روی سیستم شما

به عنوان یک پیشنهاد، این مقاله نشان می دهد که چگونه الگوریتم های آوایی مختلف را در یک رویکرد برداری شده ترکیب کنیم و از ویژگی های آنها برای دستیابی به نتیجه مقایسه بهتری نسبت به استفاده از الگوریتم های منفرد به طور جداگانه استفاده کنیم. برای پیاده سازی این، کتابخانه مبتنی بر پایتون به نام جستجوی پیشرفته AdvaS روی SourceForge وارد بازی می شود. AdvaS قبلاً شامل روشی برای محاسبه چندین کد آوایی برای یک کلمه در یک مرحله است.

توضیح الگوریتم های آوایی

به بیان دقیق تر، هر یک از این الگوریتم ها نمایش آوایی خاصی از یک کلمه ایجاد می کنند. معمولاً چنین نمایشی یا یک رشته با طول ثابت یا یک رشته با طول متغیر است که فقط از حروف تشکیل شده است یا ترکیبی از حروف و ارقام است. ساختار دقیق نمایندگی بستگی دارد روی الگوریتم. در واقع، اگر دو نمایش – که با استفاده از یک الگوریتم محاسبه می‌شوند – مشابه باشند، دو کلمه اصلی بدون توجه به اینکه چگونه نوشته شده‌اند به یک شکل تلفظ می‌شوند. در واقع، این به تشخیص کلمات مشابه کمک می کند، حتی اگر املای متفاوتی داشته باشند – مهم نیست که انجام شود. روی هدف یا تصادفی

هر کدام از این الگوریتم ها با زبان یا هدف خاصی طراحی شده اند و دقیقاً به یک شکل در زبان یکدیگر نمی گنجند. به خاطر داشته باشید که نمایش‌ها همیشه بهینه نیستند، اما در نظر گرفته شده‌اند که تا حد امکان به هم نزدیک شوند. به عنوان مثال، الگوریتم اصلی Soundex تمرکز دارد روی زبان انگلیسی، در حالی که Kölner Phonetik تمرکز دارد روی زبان آلمانی، که شامل umlauts، و دیگر کاراکترهای خاص مانند “ß” است.

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

ساندکس

نمایش حاصل از الگوریتم Soundex یک کلمه چهار حرفی است. این مبتنی است روی یک کاراکتر به دنبال سه رقم عددی. به عنوان مثال، مقدار Soundex “Knuth” K530 است که مشابه “Kant” است. این سادگی منجر به چندین بازنمایی گمراه کننده می شود. اگرچه، به طور کلی نتایج بسیار خوب است. Soundex که در اصل برای انگلیسی آمریکایی طراحی شده بود، امروزه در نسخه های مختلف زبانی مانند موجود است فرانسوی، آلمانی و عبری.

Soundex که توسط رابرت سی راسل و مارگارت کینگ اودل در آغاز قرن بیستم توسعه یافت، با در نظر گرفتن زبان انگلیسی طراحی شد. این به طور گسترده ای برای شناسایی نام های خانوادگی مشابه به عنوان بخشی از سرشماری ایالات متحده در دهه 1930 استفاده شد.

متافون

توسط لارنس فیلیپس در سال 1990 توسعه یافت. متافون همچنین با در نظر گرفتن زبان انگلیسی طراحی شده است. او سعی کرد با استفاده از اطلاعات مکانیسم Soundex را بهبود بخشد روی تغییرات و ناهماهنگی در املا / تلفظ انگلیسی برای تولید رمزگذاری دقیق تر. در نتیجه نمایش آوایی یک کلمه با طول متغیر است روی 16 صامت “0BFHJKLMNPRSTWXY”. 5 مصوت “AEIOU” نیز مجاز هستند، اما فقط در ابتدای نمایش.

توصیف اصلی الگوریتم متافون نسبتاً نادرست بود و منجر به توسعه دو متافون و متافون 3 شد. الگوریتم دومی می‌تواند هزاران کدگذاری اشتباه را که توسط دو نسخه اول تولید شده‌اند تصحیح کند. Metaphone 3 به عنوان یک نرم افزار تجاری در دسترس است و از تلفظ آلمانی و اسپانیایی پشتیبانی می کند.

شکل 1 در زیر یک اسکرین شات گرفته شده از a وب سایت شجره نامه هلندی، و نمایش های مختلف Soundex، Metaphone، و Double Metaphone را برای نام “Knuth” نشان می دهد. همچنین، شکل مجموعه‌ای از کلمات را نشان می‌دهد که به یک شکل نشان داده شده‌اند و کد آوایی یکسانی دارند (“Gleiche Kodierung wie”). هرچه الگوریتم متمایزتر باشد، تعداد کلمات با کد آوایی یکسان کمتر است.

شکل 1

به عنوان مثال، الگوریتم متافون تنها بخشی استاندارد از چند زبان برنامه نویسی است PHP. برای پایتون، هم متافون و هم متافون دوگانه بخشی از آن هستند بسته فونتیک. پیاده سازی های تجاری برای زبان های برنامه نویسی C++، C#، Java، Python و Ruby.

کاورفون

این کاورفون الگوریتم توسط دیوید هود در سال 2002 ایجاد شد. نسخه اصلاح شده آن در سال 2004 منتشر شد. محیط پروژه پروژه Caversham در دانشگاه اوتاگو، نیوزلند. پیش‌زمینه الگوریتم کمک به تطبیق داده‌های فهرست‌های انتخاباتی بین اواخر قرن نوزدهم و اوایل قرن بیستم بود، جایی که نام‌ها فقط باید در یک فرم معمولاً قابل تشخیص. این الگوریتم به نام شهرداری که دانشگاه در آن واقع شده است، نامگذاری شده است، و برای ترکیب حروف خاص زبان که در آن تحقیق اسامی انجام شده است، بهینه شده است.

به طور پیش فرض، الف Caverphone نمایش شامل شش کاراکتر و اعداد است. برخی از پیاده سازی ها اجازه می دهد تا طول را تا ده کاراکتر و اعداد افزایش دهید. به عنوان مثال، “Thompson” به کد “TMPSN1” تبدیل می شود. در حال حاضر، این الگوریتم برای C#، Python (نسخه اصلاح شده)، جاوا (هر دو نسخه اصلی و اصلاح شده) و R موجود است.

سیستم شناسایی و اطلاعات ایالت نیویورک

این الگوریتم در دهه 1970 به عنوان بخشی از توسعه داده شد سیستم شناسایی و اطلاعات ایالت نیویورک (NYSIIS). گفته می شود که امروزه هنوز از کیفیت آن استفاده می شود به الگوریتم Soundex نزدیک است.

این طرح به گونه ای بهینه شده بود که به طور خاص با نام های آمریکایی مطابقت داشته باشد. بنابراین، دو نام “Webberley” و “Wibberley” با رمز آوایی “WABARLY” نشان داده می شوند.

Kölner Phonetik

مستقر روی الگوریتم ساندکس در سال 1969 هانس یواخیم پستل این الگوریتم را توسعه داد Kölner Phonetik. این زبان آلمانی را هدف قرار داده است و بعداً بخشی از سیستم های SAP شد. نمایش آوایی فقط یک رشته اعداد با طول متغیر است.

در حال حاضر، پیاده سازی در Perl، PHP، و جاوا اسکریپت شناخته شده است.

رویکرد رتبه بندی مطابقت

این رویکرد رتبه بندی مسابقه کدکس (MRA) در سال 1977 توسط وسترن ایرلاینز توسعه یافت. ایده این بود که اسامی همفون را شناسایی کنیم روی لیست مسافران با تمرکز قوی روی زبان انگلیسی. به عنوان مثال، نمایش برای “Smith” “SMTH” است، در حالی که “Smyth” توسط “SMYTH” رمزگذاری شده است.

در حال حاضر، MRA به عنوان یک در دسترس است پیاده سازی سی شارپ از یک وب سایت آرشیو شده، و به عنوان یک روش پایتون در ماژول چتر دریایی.

پیاده سازی

محاسبه درجه تشابه مبتنی است روی سه بردار به عنوان codeList1، codeList2، و weight در فهرست کد منبع زیر. در پایتون یک برداری را می توان به عنوان یک آرایه پیاده سازی کرد، برای مثال با استفاده از NumPy بسته بندی بردار شماره یک و دو نشان دهنده کد آوایی دو کلمه مختلف است. بردار شماره سه وزن الگوریتم خاص را نشان می دهد و شامل یک مقدار کسری بین 0 و 1 برای توصیف آن وزن است. مجموع مقادیر منفرد بردار سه مقدار دقیق 1 است و نباید کمتر یا بیشتر از آن باشد. در صورتی که این اتفاق بیفتد، مقادیر منفرد بردار سه باید از قبل نرمال شوند.

شکل 2 سه بردار را نمایش می دهد.

شکل 2 سه بردار برای نگهداری داده ها استفاده می شود

درجه تشابه محاسبه شده بین دو کلمه بر اساس یک مقدار اعشاری است روی محاسبه به ازای هر الگوریتم آوایی (مجموع فرعی). هر خرده کل حاصل فاصله لونشتاین بین نمایش آوایی خاص است codeList1 و codeList2و وزن مربوط به الگوریتم آوایی خاص. برای NYSIIS به صورت زیر محاسبه می شود:

nysiis = Levenshtein(codeList1("nysiis"), codeList2("nysiis")) * weight("nysiis")
       = Levenshtein("Knatt", "Kand") * 0.1
       = 3 * 0.1
       = 0.3

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

کد پایتون زیر از کلاس Phonetics از ماژول AdvaS و همچنین ماژول NumPy استفاده می کند. تعریف تابع لونشتاین مشابه مقاله قبلی است روی فاصله Levenshtein، و فقط برای کامل بودن درج شده است. در مرحله بعد، سه بردار همانطور که در نشان داده شده است مقداردهی اولیه می شوند شکل 2، جمع های فرعی در یک حلقه محاسبه می شوند و کل با استفاده از آن چاپ می شود stdout.

from phonetics import Phonetics
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
                )
    return (matrix(size_x - 1, size_y - 1))



word1 = Phonetics("Knuth")
word2 = Phonetics("Kant")
print ("Comparing %s with %s" % (word1.getText(), word2.getText()))


codeList1 = word1.phoneticCode()
codeList2 = word2.phoneticCode()


weight = {
    "soundex": 0.2,
    "caverphone": 0.2,
    "metaphone": 0.5,
    "nysiis": 0.1
}


algorithms = ("soundex", "caverphone", "metaphone", "nysiis")


total = 0.0
for entry in algorithms:
    code1 = codeList1(entry)
    code2 = codeList2(entry)
    lev = levenshtein (code1, code2)
    currentWeight = weight(entry)
    print ("comparing %s with %s for %s (%0.2f: weight %0.2f)" % (code1, code2, entry, lev, currentWeight))
    subtotal = lev * currentWeight
    total += subtotal

print ("total: %0.2f" % total)

با فرض اینکه کد منبع در فایل ذخیره شده است phonetics-vector.py خروجی به شرح زیر است:

$ python phonetics-vector.py
Comparing Knuth with Kant
comparing K530 with K530 for soundex (0.00: weight 0.20)
comparing KNT1111111 with KNT1111111 for caverphone (0.00: weight 0.20)
comparing n0h with nt for metaphone (2.00: weight 0.50)
comparing Knatt with Kand for nysiis (3.00: weight 0.20)
total: 1.60
$

هر چه میزان تشابه کمتر باشد، این دو کلمه از نظر تلفظ یکسان تر هستند. همانطور که در مثال بالا “Knuth” و “Kant” نشان داده شد، مقدار محاسبه شده 1.6 و بسیار کم است.

نتیجه

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

سپاسگزاریها

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