Did You Mean SoundEx Agorithm
Selamlar;
Bugün google’ın meşhur did you mean mantığından bahsedeceğiz. SoundEx algoritması olarak da bilinen yapı için bir webapi servisi ve kullanıcı arayüzü olarak mvc ile knockoutjs javascript framework’ü kullanıcağız. Database işlemleri için codefirst’den faydalanacağız.
Bu algoritmanın oluşturulmasındaki amaç; telaffuzları benzeşen kelimelerin bu yolla aynı karakter koduna dönüştürülmeleri ve benzer kelimelerin yazımlarında farklılık olsa bile özdeşleştirilmelerinin sağlanmasıdır. SoundEx aslında bir kelimeden fonetik bir kod cikarma yontemidir. İki soundex degeri kiyaslanarak iki kelimenin birbirine ne kadar yakin okundugu cikarilabilir.
Tabi bu algoritmanın kabul görmüş belli kuralları vardır. Şimdi onları inceleyelim:
- Karakter katarının ilk harfi alınır.
- Eğer ilk harf “a, e, h, i, o, u, w, y” harflerinden herhangi biri değilse, bu harfler string değerden silinir.
- Sırasıyla tüm harflere aşağıdaki numaralar atanır.
b, f, p, v = 1
c, g, j, k, q, s, x, z = 2
d, t = 3
l = 4
m, n = 5
r = 6 - Eğer numaralandırmada aynı numarayı almış iki ya da daha fazla harf yan yanaysa (ilk işlemden önce) ya da bu harflerin arasında h veya w harfi varsa aynı olanlar çıkartılır.
- İlk dört karakteri sonuç olarak döndürülür; eğer sonuç dört karakterden az çıkarsa, dört karaktere tamamlamak amacı ile sona sıfırlar eklenir. (örn. E33 > A330).
Aşağıda bu kurallar üzerinden oluşturulmuş gelen string’in soundex algoritmasına uygun fonetik kodu çıkaran class’ı görüyorsunuz.
Image Source: https://www.codeproject.com/KB/recipes/soundex/ISoundEx.gif
SoundExtension.cs:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Text.RegularExpressions; using System.Web; namespace WebApiSoundEx.Controllers { public static class SoundexExtension { public static string Soundex(this string s) { return Soundex(s, 4); } public static string Soundex(this string s, int length) { return FullSoundex(s) .PadRight(length, '0') .Substring(0, length); } public static string FullSoundex(this string s) { const string chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; const string codes = "0123012D02245501262301D202"; Regex hwBeginString = new Regex("^D+"); Regex simplify = new Regex(@"(\d)\1*D?\1+"); Regex cleanup = new Regex("[D0]"); s = s.ToUpper(); StringBuilder coded = new StringBuilder(); for (int i = 0; i < s.Length; i++) { int index = chars.IndexOf(s[i]); if (index >= 0) coded.Append(codes[index]); } string result = coded.ToString(); result = simplify.Replace(result, "$1").Substring(1); result = hwBeginString.Replace(result, string.Empty); result = cleanup.Replace(result, string.Empty); return string.Format("{0}{1}", s[0], result); } } } |
Aşağıda görüldüğü gibi Webapi projemizde bir aranacak oyunların tam listesini dönen Get() method’u bir de aranacak oyunun soundex algoritmasına tabi tutulacak Post() method’u görülmektedir.
Webapi servis’inde cross domain’i sağlamak için Class’ın başına alttaki attribute’u koymayı unutmuyoruz.
[EnableCors(origins: “*”, headers: “*”, methods: “*”)]
Get() method’unda oyunların isimlerini string olarak tutacak static bir List<string> kullanılmıştır. Amaç her request’de liste için bir daha database’e gitmemektir. Post() method’unda static List<tblGame> kullanımaktadır. Burada amaç gene database’e olabilecek yükü engellemektir. Database’den çekilen tüm oyun isimleri sıra ile soundex algoritması uygulanıp fonetik kodu çıkarılır. Ve aranan string ifadenin gene soundex algoritması uygulanıp alınan fonetik kodu ile karşılaştırılır. Aynı olan kod’a karşılık gelen oyun ismi geriye döndürülür.
SoundExController:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
using DAL; using System; using System.Collections.Generic; using System.Linq; using System.Net; using System.Net.Http; using System.Web.Http; using System.Web.Http.Cors; namespace WebApiSoundEx.Controllers { [EnableCors(origins: "*", headers: "*", methods: "*")] public class SoundExController : ApiController { public static List<string> list = new List<string>(); public List<string> Get() { if (list.Count() == 0) { using (GameShop db = new GameShop()) { gameList = db.tblGames.ToList(); } foreach (tblGames gameItem in gameList) { list.Add(gameItem.Name); } } return list; } public static List<tblGames> gameList; public string Post([FromBody] string game) { if (gameList == null) { using (GameShop db = new GameShop()) { gameList = db.tblGames.ToList(); } } foreach (tblGames gameItem in gameList) { if (SoundexExtension.Soundex(gameItem.Name) == SoundexExtension.Soundex(game)) { return gameItem.Name; break; } } return ""; } } } |
DAL projesine ailt CodeFirst kodları: Aşağıda görüldüğü gibi tblCategory ve tblGames adında 2 tablo vardır. Bu tabloları GameShop adında bir dbcontext altında eşleştirilmiştir.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 |
namespace DAL { using System; using System.Collections.Generic; using System.ComponentModel.DataAnnotations; using System.ComponentModel.DataAnnotations.Schema; using System.Data.Entity.Spatial; [Table("tblCategory")] public partial class tblCategory { public tblCategory() { tblGames = new HashSet<tblGames>(); } public int ID { get; set; } [StringLength(50)] public string CategoryName { get; set; } public bool? isEnable { get; set; } public virtual ICollection<tblGames> tblGames { get; set; } } public partial class tblGames { public int ID { get; set; } [StringLength(50)] public string Name { get; set; } public decimal? Price { get; set; } public int? CategoryID { get; set; } [StringLength(50)] public string ImageUrl { get; set; } public virtual tblCategory tblCategory { get; set; } } } namespace DAL { using System; using System.Data.Entity; using System.ComponentModel.DataAnnotations.Schema; using System.Linq; public partial class GameShop : DbContext { public GameShop() : base("name=GameShop") { } public virtual DbSet<tblCategory> tblCategory { get; set; } public virtual DbSet<tblGames> tblGames { get; set; } protected override void OnModelCreating(DbModelBuilder modelBuilder) { modelBuilder.Entity<tblCategory>() .Property(e => e.CategoryName) .IsUnicode(false); modelBuilder.Entity<tblCategory>() .HasMany(e => e.tblGames) .WithOptional(e => e.tblCategory) .HasForeignKey(e => e.CategoryID); modelBuilder.Entity<tblGames>() .Property(e => e.Name) .IsUnicode(false); modelBuilder.Entity<tblGames>() .Property(e => e.Price) .HasPrecision(18, 3); modelBuilder.Entity<tblGames>() .Property(e => e.ImageUrl) .IsUnicode(false); } } } |
Aşağıda knockoutjs için ilgili viewModelimiz tanımlanmıştır. Amaç yukarıdaki örneklerden de anlaşılacağı gibi aranacak oyunun girilmesi ve girilen bu oyunun yazımına en yakın oyun isminin aşağasında 3 karakter girildikten sonra aranıp gösterilmesidir. Bir de en altta aranacak tüm oyun listesi ilk karakter girişi yapıldıktan sonra dolmaktadır. İlgili oyun bulununca listedeki o oyun seçilmektedir. Tüm bu işlemler MVVM design patterin ile knockoutjs yardımı ile yapılmaktadır. Tanımlanan viewModel’de aranacak text searchText property’si olarak tanımlanmıştır. Bulunan oyun ismi result property’si olarak tanımlanmıştır. Başta çekilecek oyun listesi ise listGame observableArray olarak tanımlanmıştır.
<input data-bind=”value: searchText,event: { keyup: send },valueUpdate: ‘afterkeydown'”>
Yukarıda görüldüğü gibi SearchText’in bağladığı property yani viewModel’deki karşılığı data-bind property’si ile searchText olarak gösterilmiştir. Ayrıca keyup eventinde gene viewModel’in bir property’si olan send() function’ı çağrılmaktadır. Bu function’da girilen karakter sayısı 2’den büyükse webapi servisimize post işlemi yapılmaktadır. Ayrıca girilen ilk karakter ise viewModel’in bir diğer property’si olan getList() function’ı çağrılmakta ve tüm oyun listesi data-bind=”options:listGame, value: result” şeklinde yine viewModel’in bir property’si olan listGame’e bağlanmış bir select listesine basılmaktadır.
Index.cshtml:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 |
@{ ViewBag.Title = "Index"; } <script src="~/Scripts/jquery-2.1.1.min.js"></script> <script src="~/Scripts/knockout.js"></script> <script> function viewModel() { var self = this; self.searchText = ko.observable(""), self.result = ko.observable(""), self.listGame = ko.observableArray(), self.getList = function () { $.ajax({ type: 'GET', url: 'http://localhost:5683/api/SoundEx', contentType: "application/json; charset=utf-8", traditional: true, success: function (gameList) { for (var i = 0; i < gameList.length; i++) { self.listGame.push(gameList[i]); } } }); } self.send = function () { if (self.listGame().length == 0) { self.getList(); } if (self.searchText().length > 2) { $.ajax({ type: 'POST', url: 'http://localhost:5683/api/SoundEx', data: ko.toJSON(searchText), contentType: "application/json; charset=utf-8", traditional: true, success: function (data) { if (data != "") { self.result(data); } else { self.result(""); } } }); } else { self.result(''); } } }; $(document).ready(function () { ko.applyBindings(viewModel()); }); </script> <h2>Index</h2> <p>Search Text:<input data-bind="value: searchText,event: { keyup: send },valueUpdate: 'afterkeydown'"></input></p> <p>Did U Mean:<input data-bind="value: result" readonly="readonly"></input></p> Full List <select multiple="multiple" style="height:250px" data-bind="options:listGame, value: result"> </select> |
İstenirse soundex algorithm’ası Sql tarafından’da uygulanarak çözüme gidilebilir. Örnek query’ler aşağıdadır.
|
1 2 3 4 |
select * from [GameShop].[dbo].[tblGames] where SOUNDEX(Name)= SOUNDEX('super sitrit fayter') select * from [GameShop].[dbo].[tblGames] where SOUNDEX(Name)= SOUNDEX('doblo') select * from [GameShop].[dbo].[tblGames] where SOUNDEX(Name)= SOUNDEX('desdini cild') select * from [GameShop].[dbo].[tblGames] where SOUNDEX(Name)= SOUNDEX('walkn ded') |
Yukarıdaki örnekde de görüldüğü gibi aranacak text her ne olursa olsun tam olarak doğru yazılmasa da buna en yakın sonuçlar kullanıcıya sunulabilmektedir. Bu da işleri büyük oranda kolaylaştırmaktadır.
Bir sonraki makalede görüşmek üzere hoşçakalın.
Source Code:http://www.borakasmer.com/projects/WebApiSoundEx.rar
Source:
Merhabalar Hocam,
yazınızı çok beğendim, kullanmayı düşünüyorum SoundEx algoritmasını. “Get() method’unda oyunların isimlerini string olarak tutacak static bir List kullanılmıştır. Amaç her request’de liste için bir daha database’e gitmemektir.” demişsiniz, bunu kullanmamızın sakıncası var mıdır? Listeye yeni kayıt eklendiğinde ne yapmamız gerekecek bu durumda.
Selam Musa,
Öncelikle teşekkürler.
Sürekli yeni kayıt eklenecek veya çıkarılacak hatta güncellenecek ise Redis gibi distiributed bir cache, eğer liste çok uzun olacak ise elasticsearch ya da MongoDB, CosmosDB, Firebase gibi Document DBler kullanman daha sağlıklı olabilir. Statick List, senin en başta doldurduğun her client’ın ortak kullandığı, memoryde tutulan bir nesnedir. Ve uygulama kapanana kadar memoryde duru. Bu listeye de eleman sayısı çok olmamak kaydı ile istediğin kelimeyi ekleyip çıkarabilirsin.
İyi çalışmalar..