MapReduce'a Dayalı Üçlü N-gram Algoritmasının Paralelleştirilmesi Üzerine Araştırma
"İnternet +" çağının ortaya çıkması ve hızla gelişmesiyle birlikte, yeni medya insanların yaşamlarının ayrılmaz bir parçası haline geldi. Birçok haber medya platformunda her gün çok sayıda orijinal haber yayınlandı ve haberlerin güncelliği bunu yapar Büyük medya tarafından geniş çapta yeniden basılmakta ve iletilmektedir ve manuel inceleme pratik değildir. Bu nedenle, sorunların "zamanında ve doğru bir şekilde" keşfedilmesini, tespit edilmesini ve çözülmesini sağlamak için makale yayınlanmadan önce anlamsal analize dayalı otomatik tanıma teknolojisi kullanılmalıdır. Gerçek kelime hatalarını tanımlamak için olasılık istatistiklerini kullanma yöntemi, kelimelerin ve kelime gruplarının üç elementli N-gram dil modelini kullanmaktır. Daha küçük bir depolama alanıyla daha yüksek bir kısıtlı N-gram yumuşatma olasılığı elde edebilir, bu da istatistiksel modelin karmaşıklığını büyük ölçüde azaltır. Sonraki eğitimin iş yükü uygundur ve uygulama alanının diline uyarlanabilirlik güçlüdür Üçlü N-gram dil modeli, Çince metnin otomatik hata kontrolünde etkilidir, ancak eğitim için büyük ölçekli bir Çince külliyat gerektirir. Bağımsız çalışmaya dayalı veri işleme yöntemi, bilgi işlem verimliliğinin iyileştirilmesini kısıtlar ve aşırı eğitim süresi ve aşırı bellek kullanımı sorunlarını çözmek zordur. Büyük verilerin işlenmesiyle karşı karşıya kalan MapReduce modeli, büyük ölçekli veri işleme işlerini bağımsız olarak çalıştırılabilir birkaç göreve ayırır. Yaygın olarak kullanılır ve paralel programlamanın zorluğunu azaltabilir ve işlem süresini büyük ölçüde kısaltabilir. Mevcut büyük ölçekli veri işleme haline gelmiştir. Temel teknoloji.
Açık kaynak dağıtılmış işleme platformu Hadoop'a dayanan bu makale, tek bir makinede uzun çalışma süresi ve üçlü N-gram algoritmasının yetersiz belleği sorunlarını çözen MapReduce çerçevesinin paralelleştirilmesini tasarlar ve uygular ve algoritma deneylerle doğrulanmıştır. İşleme hızı ve doğruluğu.
1 Model kurulması
1.1 Üçlü N-gram modelinin oluşturulması
Metin verisi işlemede, kelime materyali önce bir sıraya bölünür ve ardından sıra gruplar halinde genişletilir. Tahmin penceresinin gerçek boyutunun w'ye eşit olduğu varsayıldığında, yeni bir meta veri talebi olduğunda, daha uzun meta veri talebi bununla değiştirilir, böylece yeni bir G grubu oluşturulur. Bu süreçte 3 gramlık model uygulandığından, tüm G grupları için ilk iki dosya meta veri talebi sabit bir şekilde işlenir ve sıralı sıra için, aşağıdaki w-2 sırasız bir dizi olarak işlev görür. Gruplama bittikten sonra, elde edilen grup üzerinde standartlaştırılmış fazlalık işleme gerçekleştirilir ve düzensiz dizideki tamamen tutarlı meta veri talepleri ortadan kaldırılır. Ek olarak, işlenen gruplar sıralı bir sırayla bağlanmalıdır. Ve sonra tüm verilerden en yüksek olasılığı arayın ve bunları kurallar halinde düzenleyin; tüm kurallar önceden getirilmiş grupların kombinasyonunu standartlaştıracaktır. Spesifik algoritma açıklaması aşağıda verilecektir. Bitişik üçlü durumun olasılığını tahmin etmenin formülü şöyledir:
Formülde P, bir eşdizimlilik olasılığını temsil eder; Wi rastgele bir Çince karakteri temsil eder, Wi-1 ve Wi + 1 sırasıyla rastgele bir Çince karakterin ön ve arka Çince karakterlerini temsil eder ve Say (...) belirli bir kelime dizisini temsil eder. Tüm korpustaki kümülatif oluşum sayısı.
Şekil 1'de gösterildiği gibi, tanımlama adımları aşağıdaki gibidir:
(1) Ön işleme: Girilen bir makale için, genellikle bir TXT dosyası için, sözcükler önce bölümlere ayrılır. Bir külliyat olarak, hata olmadığından emin olmalıyız.
(2) İlk tarama: Tüm özellik dizilerini çıkarın, N-gram hesaplama modeli aracılığıyla kelimenin geçtiği N sayısını sayın ve kelimeyi ve sayılan sayıları mongo veritabanına ekleyin.
(3) İkinci tarama: P belirli bir eşikten düşük değilse, o zaman tanıma sonucunda hata yoktur ve doğru kelime üretme külliyatı olarak değerlendirilir; işlemle elde edilen kelime ve cümle güvenilirliği P eşikten düşükse difüzyon işlemi yapılabilir.
(4) Üçüncü tarama: Görünme olasılığı düşük olan kelimeleri hariç tutmak için hata tespit kurallarının özel uygulamasını gerçekleştirin, böylece genel doğruluğu optimize edin.
1.2 MapReduce modeli
MapReduce güçlü çalıştırılabilirliğe ve mükemmel hata toleransına sahip paralel bir programlama modelidir.MapReduce'a dayalı olarak tasarlanan programlar iyi bir kararlılığa ve ölçeklenebilirliğe sahiptir. Çerçevesi genellikle, çeşitli işlemleri büyük ölçekli veri kümeleri üzerinde dağıtacak olan "böl ve yönet" yaklaşımını uygular, böylece birden çok alt düğüm bunları birlikte tamamlayabilir ve ardından gerekli olanı elde etmek için tüm alt düğümlerin ara sonuçlarını entegre edebilir. sonucu. İşlemenin tüm süreci iki tür işleve dayanır: Harita işlevi ve Azaltma işlevi Birincisi görevi ayrıştırır ve ikincisi görev işlemenin sonucunu normalleştirir. Paralel programlamadaki diğer sorunlar için, daha temsili sorunlar, tümü MapReduce çerçevesi aracılığıyla standartlaştırılan dağıtılmış depolama, hataya dayanıklı işleme vb. İçerir.
MapReduce dağıtılmış veri işleme süreci Şekil 2'de gösterilmektedir. Veri girişi bağlantısında, MapReduce neredeyse aynı boyutta veri blokları elde etmek için veri miktarını eşit parçalara bölebilir. Harita görevi (genellikle Eşleyici olarak adlandırılır), belirli kullanıcı tanımlı Harita işlevlerini gerçekleştirebilir. Harita bağlantısında, tüm Harita görevleri belirli anahtar / değer çiftleri elde etmek için belirli bölmeleri işleyebilir. Harita işlevi aracılığıyla işlendikten sonra, belirlenen bir konumda depolanan ara verilerin bir parçasını oluştururlar , Belli bir seviyeye yükseltildikten sonra yerel diske aktarın. Azaltma aşamasında, Harita işlevinin veri sonucu alınır ve giriş çiftleri genişletilir ve standartlaştırılır. Çıktı bağlantısı: İşlemin sonuçlarını yazın Görevin yürütülmesi sırasında, Hadoop çerçevesi görev planlamasını etkin bir şekilde yönetecek, görevin yürütülmesini yakından izleyecek ve bazı başarısız görevleri yeniden başlatacaktır. .
2 MapReduce'a dayalı üçlü N-gram algoritma modelinin uygulanması
2.1 MapReduce'un üçlü N-gram algoritması paralelleştirme fikri
Tek bir makinede çalışan üçlü N-gram algoritmasını analiz ederek ve düzenli hesaplama modunu paralel olarak geliştirerek, MapReduce çerçevesi altında üçlü bir N-gram algoritması önerilmiştir. MapReduce çerçevesi altındaki üçlü N-gram algoritmasının kapladığı zaman uzunluğu ve bellek alanı ile geleneksel bağımsız bir makinede çalışan üçlü N-gram algoritması karşılaştırıldığında, üçlü N-gram algoritmasının MapReduce çerçevesine nakledilmesinin devasa Çince metnini gerçekleştirdiği kanıtlanmıştır. Veri kümelerinin paralel işlenmesi.
Çok sayıda Çince metin veri setini genişletmek ve işlemek için üçlü N-gram algoritması kullanıldığında, hesaplama miktarı daha yüksek bir seviyeye ulaşır ve bu da algoritmanın dezavantajı olan uzun süreli zaman tüketimine yol açar. Bu algoritma pek çok kez optimize edilmiş olmasına rağmen, üçlü N-gram algoritması, veri ölçeğinin sürekli genişlemesi ile belirli bir limiti aşan hesaplama gereksinimleri nedeniyle verimliliğini düşürmüştür. Bu nedenle, algoritma "böl ve yönet" kavramını uygulayabilir: Hadoop'un HDFS dosya sistemi, metin verilerini depolama için aynı boyutta n veri bloğuna böler ve ardından veri bloklarını m düğümlerine gönderir, Harita işlevini çalıştırır ve her veri bloğunu tarar , Kelime birleştirme istatistiklerini oluşturmak için her kelimenin ilk iki kelime ile birlikte görünme sayısını sayarak, her veri setinin yerel veri istatistik algoritması klasik üçlü N-gram algoritması ile aynıdır; Harita aşaması Combine'da yazılır Sonuçlar birleştirilir ve daha sonra istatistiksel sonuçlar yeni bir veri seti oluşturmak için aynı kelimelere göre yeniden gruplandırılır; Azaltma fonksiyonu küresel bitişik kelimeler arasında istatistiksel olasılık sonuçlarını elde etmek için kullanılır ve olasılık istatistiksel sonuçları eşiklenir.İstatistik sonuçlara ve eşiğe göre Karşılaştırma, kelime eşdiziminin doğruluğunu belirlemek için yapılır ve yinelemeli olarak metin düzeltilmiştir.
MapReduce tabanlı üçlü N-gram algoritması, büyük ölçekli verilerin hesaplama çalışma süresini ve bellek alanına bağımlılığı büyük ölçüde kısaltır ve yürütme verimliliği, geleneksel üçlü N-gram algoritmasına kıyasla önemli ölçüde iyileştirilir.
2.2 MapReduce'un üçlü N-gram algoritması paralelleştirme stratejisi
MapReduce'un üçlü N-gram algoritmasının paralel hesaplaması, önce büyük ölçekli bir Çince metin veri kümesini, paralel işleme için belirli bir boyuttaki (varsayılan eşit bölümlü depolama için 64 MB veri boyutudur) N veri bloğuna bölmek ve ardından İstatistiksel sonuçları hesaplamak ve almak için Harita ve Azaltma işlevlerini çalıştırın.
Algoritma akışı Şekil 3'te gösterilmektedir. MapReduce programı birden fazla Map ve Reduce görevi içerir ve her Map görevi yalnızca veri blok işlemlerini gerçekleştirmekle kalmaz, aynı zamanda veri bloklarının istatistiksel sonuçlarını da okumalıdır. Üçlü N-gram algoritması, her kelimenin eşdizimini önceki ve iki kelimeyle eşlemek için Harita işlevini kullanır. < anahtar değerler > Anahtar / değer çiftleri ve ilk < anahtar1, değer1 > Anahtar / değer çiftleri göreceli sayıda Harita işlevine iletilir ve buraya birden çok Birleştirme görevi eklenir. Ana işlevi, < anahtar1, değer1 > Anahtar / değer çiftindeki aynı anahtarın değer değeri, yeni bir anahtar / değer çifti oluşturmak için toplanır < anahtar2, değer2 > Bundan sonra, Ortak aracılığıyla, aynı anahtarın anahtar-değer çiftleri yeniden eşit olarak dağıtılır ve depolanır ve aynı anahtarın anahtar-değer çiftleri aynı veri kümesinde dağıtılır. Bariyer, görevleri ücretsiz harita işlevine atamaktan sorumludur ve aynı zamanda geçmek için olasılık istatistiklerini benimser Test kelimelerini oluşturmak için ilk iki Çince karakterle her bir Çince karakterin oluşum sayısını sayın ve yerel istatistiksel sonuçlar elde etmek için Harita aşamasının sonuçlarını birleştirin.Son olarak, Harita işlevi işleminin sonuçları Azalt'a iletilir ve bölümlemeyi tamamlamak için entegrasyon işlemi gerçekleştirilir. < anahtar2, değer2 > Yeni anahtar / değer çiftleri oluşturmak için bindirme işlemi gerçekleştirin < anahtar3, değer3 > . Şekil 4'te gösterildiği gibi, istatistiksel sonuçlar < Ben 1 > < 2 seviyorum > < Çin, 3 > < Çin, 3 > Global istatistiksel sonucu alın ve karşılaştırma için eşik değerini ayarlayın ve sözcük eşdizimi sonucunu eşik değerinden daha büyük olarak doğru öğe olarak tanımlayın, böylece bir bütün oluşturun.
2.3 MapReduce'un üçlü N-gram algoritmasının paralel uygulaması
MapReduce tabanlı üçlü N-gram algoritmasına dayalı istatistiksel olasılık sonuçları elde etmek için özel uygulama süreci aşağıdaki gibidir:
(1) Çince metin veri setinde düğüm segmentasyonu gerçekleştirin. InputFormat, aynı boyutta n veri bloğu elde etmek için metin içeriğini böler ve bunları aynı anda biçimlendirir. < anahtar değerler > Anahtar-değer çiftleri (anahtar bölümleme numarasıdır ve değerler bölümlemenin gerçekleşme sayısıdır), bundan sonra veri bloğu m düğüme iletilir.
(2) Harita programını başlatın, tüm veri bloklarını tarayın ve anahtar / değer çiftlerini belirli
