kök salmak - Stemming

Kayak tekniği için bkz Stem (kayak) . Tırmanma tekniği için, bkz . Tırmanma terimleri sözlüğü § gövde .

Olarak dilsel morfolojisi ve bilgi alma , kaynaklanan kendi için çekimli (ya da bazen türetilmiş) kelime indirgeme işlemidir kelime kök , baz ya da kök form, genel olarak bir yazılı sözcük biçiminde. Kökün , kelimenin morfolojik köküyle aynı olması gerekmez ; bu kök kendi içinde geçerli bir kök olmasa bile, ilgili sözcüklerin aynı kökle eşlenmesi genellikle yeterlidir. Kök alma algoritmaları 1960'lardan beri bilgisayar bilimlerinde çalışılmaktadır . Birçok arama motoru , aynı köke sahip sözcükleri eş anlamlı sözcüklerle bir tür sorgu genişletmesi olarak ele alır ; bu işlem, birleştirme adı verilen bir işlemdir.

Kelimeden türeyen bir bilgisayar programı veya alt yordamı , kök ayırma programı , kök ayırma algoritması veya kök ayırıcı olarak adlandırılabilir .

Örnekler

Kök üzerindeki İngiliz işletim için bir sözcük kökü ayırıcı kedi böyle belirlemelidir dizeleri olarak kediler , kedi gibi ve catty . Bir saplama algoritması ayrıca balık tutma , balık tutma ve balıkçı sözcüklerini sap balığa indirgeyebilir . Kök ihtiyacı Porter algoritması, azaltan örneğin kelime, olmayacak iddia , iddia , iddia , savunarak ve argus kök için Argu .

Tarih

İlk basılan kök saplayıcı , 1968'de Julie Beth Lovins tarafından yazılmıştır . Bu makale, erken tarihli olması nedeniyle dikkat çekicidir ve bu alandaki daha sonraki çalışmalar üzerinde büyük etkisi olmuştur. Makalesi , Princeton Üniversitesi'nden Profesör John W. Tukey tarafından , Harvard Üniversitesi'nde Profesör Gerard Salton başkanlığında Michael Lesk tarafından geliştirilen algoritmayı ve James L. Dolby tarafından geliştirilen üçüncü bir algoritmayı, daha önceki üç büyük algoritma girişimine atıfta bulunuyor. Ar-Ge Danışmanları, Los Altos, California.

Daha sonraki bir kök ayırıcı Martin Porter tarafından yazılmıştır ve Program dergisinin Temmuz 1980 sayısında yayınlanmıştır . Bu kök ayırıcı çok yaygın olarak kullanıldı ve İngilizce kök ayırma için kullanılan fiili standart algoritma haline geldi. Dr. Porter, kaynak bulma ve bilgi alma konusundaki çalışmaları nedeniyle 2000 yılında Tony Kent Strix ödülünü aldı.

Porter kök çıkarma algoritmasının birçok uygulaması yazıldı ve serbestçe dağıtıldı; ancak bu uygulamaların çoğu ince kusurlar içeriyordu. Sonuç olarak, bu kök ayırıcılar potansiyelleriyle eşleşmedi. Bu hata kaynağını ortadan kaldırmak için, Martin Porter, 2000 yılı civarında algoritmanın resmi bir özgür yazılım (çoğunlukla BSD lisanslı) uygulamasını yayınladı. Bu çalışmayı önümüzdeki birkaç yıl içinde , stemming algoritmaları yazmak için bir çerçeve olan Snowball'u inşa ederek genişletti ve diğer birkaç dil için kök ayırıcılarla birlikte geliştirilmiş bir İngilizce kök dizgesi uyguladı.

Paice-Husk Stemmer, 1980'lerin sonlarında Lancaster Üniversitesi'nde Chris D Paice tarafından geliştirildi , yinelemeli bir kök ayırıcıdır ve harici olarak depolanmış bir dizi kök alma kuralına sahiptir. Standart kurallar dizisi "güçlü" bir kök sağlar ve bir sonun kaldırılmasını veya değiştirilmesini belirtebilir. Değiştirme tekniği, kısmi eşleştirmeyi yeniden kodlamak veya sağlamak için süreçte ayrı bir aşamaya olan ihtiyacı ortadan kaldırır. Paice ayrıca, fazla ve eksik saplama hatalarını saymaya dayalı kök saplayıcıları karşılaştırmak için doğrudan bir ölçüm geliştirdi.

algoritmalar

Bilgisayar biliminde çözülmemiş problem :

İngilizce dilinde herhangi mükemmel bir kök alma algoritması var mı?

(bilgisayar biliminde daha çözülmemiş problemler)

Performans ve doğruluk ve belirli engelleme engellerinin nasıl aşıldığına göre farklılık gösteren birkaç tür saplama algoritması vardır.

Basit bir kök ayırıcı , bir arama tablosunda çekimli formu arar . Bu yaklaşımın avantajları basit, hızlı olması ve istisnaları kolayca ele almasıdır. Dezavantajları, çekimli tüm biçimlerin tabloda açıkça listelenmesi gerektiğidir: yeni veya tanıdık olmayan kelimeler, tamamen düzenli olsalar bile (örneğin, cat ~ cat) ele alınmaz ve tablo büyük olabilir. İngilizce gibi basit morfolojiye sahip diller için tablo boyutları mütevazıdır, ancak Türkçe gibi yüksek çekimli diller her kök için yüzlerce potansiyel çekimli biçime sahip olabilir.

Bir arama yaklaşımı, aşırıya kaçmayı önlemek için ön konuşma bölümü etiketlemesini kullanabilir.

üretim tekniği

Bir kök ayırıcı tarafından kullanılan arama tablosu genellikle yarı otomatik olarak üretilir. Örneğin, kelime "çalıştır" ise, ters çevrilmiş algoritma otomatik olarak "çalışıyor", "çalışıyor", "çalışıyor" ve "çalışıyor" formlarını oluşturabilir. Son iki form geçerli yapılardır, ancak olası değildir..

Sonek-sıyırma algoritmaları

Sonek çıkarma algoritmaları, çekimli formlar ve kök form ilişkilerinden oluşan bir arama tablosuna dayanmaz. Bunun yerine, tipik olarak daha küçük bir "kurallar" listesi depolanır ve bu liste, bir giriş sözcüğü biçimi verildiğinde, algoritmanın kök biçimini bulması için bir yol sağlar. Kuralların bazı örnekleri şunları içerir:

  • kelime 'ed' ile bitiyorsa, 'ed' kelimesini kaldırın
  • kelime 'ing' ile bitiyorsa, 'ing' kelimesini kaldırın
  • kelime 'ly' ile bitiyorsa, 'ly'yi kaldırın

Sürdürücünün dilbilim, morfoloji ve sonek çıkarma kurallarını kodlamanın zorlukları konusunda yeterince bilgili olduğu varsayıldığında, sonek çıkarma yaklaşımlarının bakımı kaba kuvvet algoritmalarından çok daha basit olma avantajına sahiptir. Sonek çıkarma algoritmaları, istisnai ilişkilerle ('koşma' ve 'çalışma' gibi) uğraşırken düşük performans nedeniyle bazen kaba olarak kabul edilir. Ek çıkarma algoritmaları tarafından üretilen çözümler , birkaç istisna dışında iyi bilinen eklere sahip olan sözlüksel kategorilerle sınırlıdır . Ancak bu, konuşmanın tüm bölümlerinin bu kadar iyi formüle edilmiş bir dizi kurala sahip olmadığı için bir sorundur. Lemmatization , bu zorluğun üstesinden gelmeye çalışır.

Ön ek sıyırma da uygulanabilir. Tabii ki, tüm diller önek veya son ek kullanmaz.

Ek algoritma kriterleri

Sonek çıkarma algoritmaları, çeşitli nedenlerle sonuçlarda farklılık gösterebilir. Bunun bir nedeni, algoritmanın, çıktı kelimesinin verilen dilde gerçek bir kelime olup olmayacağını kısıtlamasıdır. Bazı yaklaşımlar, kelimenin dil sözlüğünde (dildeki tüm kelimelerin kümesi) fiilen var olmasını gerektirmez. Alternatif olarak, bazı sonek çıkarma yaklaşımları, gerçek kelimeler olarak var olan bilinen tüm morfolojik kelime köklerinin bir veritabanını (geniş bir liste) tutar. Bu yaklaşımlar, bir karar vermeden önce terimin varlığı için listeyi kontrol eder. Tipik olarak, terim mevcut değilse, alternatif işlem yapılır. Bu alternatif eylem, birkaç başka kriteri içerebilir. Bir çıktı teriminin olmaması, algoritmanın alternatif sonek çıkarma kurallarını denemesine neden olabilir.

Aynı giriş terimine iki veya daha fazla son ek çıkarma kuralının uygulanması, hangi kuralın uygulanacağı konusunda bir belirsizlik yaratabilir. Algoritma (insan eliyle veya stokastik olarak) bir kurala veya diğerine bir öncelik atayabilir. Veya algoritma, bir kural uygulamasını, var olmayan bir terimle sonuçlanırken diğer örtüşen kuralın olmadığı için reddedebilir. Örneğin, İngilizce friendlies terimi verildiğinde, algoritma ies son ekini tanımlayabilir ve uygun kuralı uygulayabilir ve friendl sonucunu elde edebilir . Friendl muhtemelen sözlükte bulunmaz ve bu nedenle kural reddedilir.

Temel sonek soyma üzerine bir gelişme, sonek ikamesinin kullanılmasıdır. Sıyırma kuralına benzer şekilde, bir ikame kuralı, bir son eki alternatif bir son ek ile değiştirir. Örneğin, ies'i y ile değiştiren bir kural olabilir . Bunun algoritmayı nasıl etkilediği, algoritmanın tasarımına göre değişir. Örneklemek için, algoritma hem ies son eki çıkarma kuralının hem de sonek ikame kuralının geçerli olduğunu belirleyebilir. Sıyırma kuralı sözlükte var olmayan bir terimle sonuçlandığından, ancak ikame kuralı olmadığı için yerine ikame kuralı uygulanır. Bu örnekte, dostluklar dostça yerine dostça olur ' .

Ayrıntılara daha fazla dalmak için yaygın bir teknik, kuralları döngüsel bir şekilde (bilgisayar bilimcilerinin söyleyeceği gibi yinelemeli olarak) uygulamaktır. Bu örnek senaryoda son ek ikame kuralı uygulandıktan sonra, dostça terimiyle ilgili eşleştirme kurallarını belirlemek için ikinci bir geçiş yapılır , burada ly sıyırma kuralı muhtemelen belirlenir ve kabul edilir. Özetle, dostluklar (değiştirme yoluyla) dostça olur, bu da (sıyırma yoluyla) arkadaş olur .

Bu örnek ayrıca kural tabanlı yaklaşım ile kaba kuvvet yaklaşımı arasındaki farkı göstermeye yardımcı olur. Bir kaba kuvvet yaklaşımında, algoritma yüzbinlerce çekimli sözcük biçimi kümesinde dost sözcükleri arayacak ve ideal olarak karşılık gelen kök biçimi arkadaşını bulacaktır . Kural tabanlı yaklaşımda, aynı çözüm üzerinde yakınlaşmak için yukarıda belirtilen üç kural art arda uygulanacaktır. Arama algoritmaları çözüme doğrudan erişime sahipken, kural tabanlı çeşitli seçenekleri ve bunların kombinasyonlarını denemeli ve ardından hangi sonucun en iyi göründüğünü seçmelidir, çünkü kaba kuvvet yaklaşımının daha yavaş olması ihtimali vardır.

Lemmatizasyon algoritmaları

Bir kelimenin kökünü belirleme sorununa daha karmaşık bir yaklaşım lemmatizasyondur . Bu süreç, önce bir kelimenin konuşma kısmının belirlenmesini ve konuşmanın her kısmı için farklı normalleştirme kurallarının uygulanmasını içerir. Bazı dillerde kök bulma kuralları, kelimenin konuşmanın hangi bölümüne bağlı olarak değiştiğinden, kökü bulmaya çalışmadan önce konuşmanın bir kısmı tespit edilir.

Bu yaklaşım, doğru sözcük kategorisini (konuşmanın bir parçası) elde etmeye son derece bağlıdır. Belirli kategoriler için normalleştirme kuralları arasında örtüşme olsa da, yanlış kategorinin belirlenmesi veya doğru kategorinin üretilememesi, bu yaklaşımın ek çıkarma algoritmalarına göre ek faydasını sınırlar. Temel fikir, eğer kökten türetilmiş sözcük hakkında daha fazla bilgi kavrayabiliyorsa, o zaman daha doğru normalleştirme kuralları uygulayabilir (ki bu, sonek çıkarma kurallarının aksine kökü de değiştirebilir).

Stokastik algoritmalar

Stokastik algoritmalar, bir kelimenin kök biçimini belirlemek için olasılığı kullanmayı içerir. Stokastik algoritmalar, olasılıksal bir model geliştirmek için bir kök formdan çekimli form ilişkilerine kadar bir tablo üzerinde eğitilir ("öğrenirler"). Bu model tipik olarak, doğası gereği son ek çıkarma veya lemmatizasyondakilere benzer şekilde karmaşık dil kuralları biçiminde ifade edilir. Köklendirme, eğitilen modele çekimli bir form girilerek ve modelin, en uygun kuralın uygulanmasıyla ilgili kararların veya kelimeyi köklendirmemek ve sadece aynı kelimeyi döndürmek veya iki farklı kuralı sırayla uygulayıp uygulamamak, çıktı kelimesinin doğru olma olasılığının en yüksek olduğu (yani, en küçük olma ihtimalinin) olacağı gerekçesiyle uygulanır. yanlış, tipik olarak bu şekilde ölçülür).

Bazı lemmatizasyon algoritmaları, konuşmanın birden fazla bölümüne ait olabilen bir kelime verildiğinde, olası her bölüme bir olasılık atanması bakımından stokastiktir. Bu, bağlam adı verilen çevreleyen kelimeleri dikkate alabilir veya almayabilir. Bağlamdan bağımsız gramerler herhangi bir ek bilgiyi dikkate almaz. Her iki durumda da, konuşmanın olası her bölümüne olasılıklar atandıktan sonra, konuşmanın en olası kısmı seçilir ve oradan normalleştirilmiş (kök) formu üretmek için giriş kelimesine uygun normalleştirme kuralları uygulanır.

n -gram analizi

Bazı kök çıkarma teknikleri , bir kelime için doğru kökü seçmek için bir kelimenin n-gram bağlamını kullanır .

Hibrit yaklaşımlar

Hibrit yaklaşımlar, yukarıda açıklanan yaklaşımlardan iki veya daha fazlasını birlikte kullanır. Basit bir örnek, önce kaba kuvvet kullanarak bir arama tablosuna başvuran bir sonek ağacı algoritmasıdır. Ancak, belirli bir dilde sözcükler arasındaki tüm ilişki kümesini depolamaya çalışmak yerine, arama tablosu küçük tutulur ve yalnızca "ran => run" gibi bir dakikalık "sık istisnalar" depolamak için kullanılır. Sözcük istisna listesinde değilse, son ek çıkarma veya lemmatizasyon uygulayın ve sonucu yazdırın.

Kökleri yapıştırın

Olarak dil terimi Eklerin bir ya değinmektedir ön ek veya son ek . Son eklerle uğraşmanın yanı sıra, birkaç yaklaşım da ortak önekleri kaldırmaya çalışır. Örneğin, süresiz olarak sözcüğü verildiğinde, baştaki "in"in kaldırılabilecek bir önek olduğunu belirleyin. Daha önce bahsedilen yaklaşımların çoğu geçerlidir, ancak ad eki soyma adını kullanır . Birkaç Avrupa dili için kökten gelen bir ek incelemesi burada bulunabilir.

Eşleştirme algoritmaları

Bu tür algoritmalar bir kök veritabanı kullanır (örneğin, kök sözcükleri içeren bir dizi belge). Bu kökler, yukarıda bahsedildiği gibi, mutlaka geçerli sözcüklerin kendileri değildir (daha çok, "tarama" ve "tarama"daki "kaşlar" gibi yaygın alt dizelerdir). Bir kelimeyi köklendirmek için algoritma, kelime içindeki aday kökün göreli uzunluğu gibi çeşitli kısıtlamalar uygulayarak onu veritabanındaki köklerle eşleştirmeye çalışır (böylece, örneğin, kısa ön ek olan "be" "olmak", "olmak" ve "olmak" gibi kelimelerin köküdür, "yan" kelimesinin kökü olarak kabul edilmeyecektir..

Dil zorlukları

Bu alandaki ilk akademik çalışmaların çoğu (Porter Stemmer algoritmasının önemli kullanımı ile) İngilizce diline odaklanmış olsa da, diğer birçok dil araştırılmıştır.

İbranice ve Arapça, hala kökten türetilmesi zor araştırma dilleri olarak kabul ediliyor. İngilizce kök ayırıcılar oldukça önemsizdir ("dry" fiilinin "dry" fiilinin üçüncü tekil şahıs hali, "axes", "axe" ve "axis"in çoğuludur; ancak hedef dilin morfolojisi, imlası ve karakter kodlaması daha karmaşık hale geldikçe kök ayırıcıların tasarlanması zorlaşır. Örneğin, bir İtalyan kök dizgesi İngilizce olandan daha karmaşıktır (daha fazla sayıda fiil çekimleri nedeniyle), Rusça olanı daha karmaşıktır (daha fazla isim çekimi ), İbranice daha da karmaşıktır (birbirine bağlı olmayan morfoloji nedeniyle , bir sesli harfleri olmayan yazı sistemi ve önek çıkarma gereksinimi: İbranice kökler iki, üç veya dört karakter olabilir, ancak daha fazla olamaz), vb.

Çok dilli köklendirme

Çok dilli köklendirme, bir arama sorgusunu yorumlarken yalnızca tek bir dil için kurallar yerine iki veya daha fazla dilin morfolojik kurallarını aynı anda uygular. Çok dilli köklendirme kullanan ticari sistemler mevcuttur.

Hata metrikleri

Sapma algoritmalarında iki hata ölçümü vardır, aşırıya kaçma ve eksik belirleme. Overstemming, iki ayrı çekimli kelimenin aynı kökten geldiği, ancak olmaması gereken bir hatadır - yanlış bir pozitif . Understemming, iki ayrı çekimli kelimenin aynı kökten türetilmesi gereken, ancak yanlış bir negatif olmayan bir hatadır . Stemming algoritmaları, her tür hatayı en aza indirmeye çalışır, ancak bir türün azaltılması diğerinin artmasına neden olabilir.

Örneğin, yaygın olarak kullanılan Porter kök ayırıcı, "evrensel", "üniversite" ve "evren"den "evrenler" anlamına gelir. Bu bir abartma durumudur: bu üç kelime etimolojik olarak ilişkili olsa da, modern anlamları çok farklı alanlardadır, bu nedenle onları bir arama motorunda eşanlamlı olarak ele almak muhtemelen arama sonuçlarının alaka düzeyini azaltacaktır.

Porter kök ayırıcısında alt dallandırmaya örnek olarak "mezun" → "mezun", "mezun" → "mezun", "mezun"/"mezun" → "mezun" verilebilir. Bu İngilizce sözcük, Latin morfolojisini korur ve bu nedenle, bu yakın eşanlamlılar birbiriyle karıştırılmaz.

Uygulamalar

Köklendirme, benzer temel anlama sahip sözcükleri birlikte gruplamak için yaklaşık bir yöntem olarak kullanılır. Örneğin, "nergis"ten bahseden bir metin, muhtemelen "nergis"ten (s olmadan) bahseden bir metinle yakından ilişkilidir. Ancak bazı durumlarda, aynı morfolojik köke sahip kelimelerin, yakından ilişkili olmayan deyimsel anlamları vardır: "pazarlama" arayan bir kullanıcı, "pazarlardan" bahseden ancak "pazarlama"dan bahsetmeyen çoğu belgeden memnun olmayacaktır.

Bilgi alma

Stemmer'lar, Web arama motorları gibi sorgu sistemlerinde yaygın öğelerdir . Bununla birlikte, İngilizce sorgu sistemleri için kökten ayırmanın etkinliğinin kısa süre sonra oldukça sınırlı olduğu bulundu ve bu, erken bilgi alma araştırmacılarının genel olarak kökten ayırmayı alakasız görmelerine yol açtı . Bunun yerine, gövde yerine n-gram aramaya dayalı alternatif bir yaklaşım kullanılabilir. Ayrıca, stemmer'lar İngilizce'den başka dillerde daha fazla fayda sağlayabilir.

Alan analizi

Stemming, alan analizinde alan kelime dağarcıklarını belirlemek için kullanılır .

Ticari ürünlerde kullanım

Pek çok ticari şirket, en azından 1980'lerden beri kökten ayırma kullanıyor ve birçok dilde algoritmik ve sözcüksel kök ayırıcılar üretti.

Kartopu köklerini değişen sonuçlarla ticari sözcük sözcük köklerini ile karşılaştırılmıştır.

Google Arama, kökten gelen kelimeyi 2003 yılında benimsemiştir. Daha önce "balık" için yapılan bir arama, "balık tutma" sonucunu vermezdi. Diğer yazılım arama algoritmaları, kelime köklendirme kullanımlarında farklılık gösterir. Basitçe alt dizileri arayan programlar açıkça "balık" içinde "balık" bulacaktır, ancak "balıklar" için arama yaparken "balık" kelimesinin geçtiği yerleri bulmayacaktır.

Ayrıca bakınız

Referanslar

daha fazla okuma

Dış bağlantılar

Bu makale, 1 Kasım 2008'den önce Ücretsiz Çevrimiçi Hesaplama Sözlüğü'nden alınan ve GFDL , sürüm 1.3 veya sonraki sürümlerin "yeniden lisanslama" koşulları altında birleştirilmiş materyale dayanmaktadır .