Suffix Array

مدت ها بود قصد نوشتن مطالبی در زمینه ساختمان داده و طراحی الگوریتم را داشتم ، ولی نوشتن مطالب اینچنینی با ساخت دکمه در اندروید زمین تا آسمان فرق دارند ، معمولاً چنین مباحثی را ترجیح می دهم روی کاغذ یا پای تخته سیاه به صورت کلامی همراه با حرکات دست و پا (body language) انجام دهم ، علاوه بر این ها مغزم نیز آن پویایی و کشش دوران آغاز جوانی را ندارد (بسوزه پدر عاشقی:دی) ، با همین همه در این آموزش قصد دارم خود را بکشم تا برای اولین بار در این سایت در مورد ساختمان داده ای بسیار بسیار جذاب ، قدرتمند و کمتر شناخته شده صحبت کنم.

در این آموزش می خواهم Suffix Array را به شما معرفی کنم. ساختمان داده دیگری به نام Suffix Tree نیز وجود دارد که از لحاظ مباحث تئوری و مفهومی بسیار با این ساختمان داده ارتباط تنگاتنگی دارد که در اینجا به شرح و توضیح آن نمی پردازم (صرفاً برای اطلاع گفتم).

Suffix Array چیست؟

Suffix Array ساختمان داده ای است که اولین بار توسط Manber و Myers در سال 1990 Suffix arrays: A new method for on-line string searches منتشر شد ، این مقاله از نظر من بهترین منبع برای آشنایی و یادگیری این ساختمان داده است ، مباحث مرتبط در این مقاله بسیار عالی توضیح داده شده اند.

اما توضیح Suffix Array :

Suffix Array که از این به بعد برای سادگی به آن S.A می گویم ،چیزی نیست جز یک آرایه ساده از اعداد :D ، این ساختمان اندیس Suffix های یک رشته را بعد از مرتب شدن نگه داری می کند. یعنی چی؟

اجازه دهید ابتدا Suffix را معرفی کنم.

Suffix یا پسوند ، زیر رشته ای از یک رشته است که از اندیس i به بعد به دست می آید.

به عنوان مثال رشته زیر را در نظر بگیرید :

banana$

پسوند های این رشته به صورت زیر هستند :

Suffix i
banana$ 0
anana$ 1
nana$ 2
ana$ 3
na$ 4
a$ 5
$ 6

با فرض اینکه کاراکتر $ از همه کاراکتر ها کوچکتر باشد (حتی از a) ، اگر این پسوند ها را به صورت الفبایی مرتب کنیم نتیجه به صورت زیر خواهد بود :

Suffix i
$ 6
a$ 5
ana$ 3
anana$ 1
banana$ 0
na$ 4
nana$ 2

آرایه ای که اندیس این Suffix ها را بعد از مرتب سازی نگه داری می کند ساختمان داده Suffix Array نامیده می شود.

به عبارتی :

Suffix Array آرایه ای از اندیس Suffix های یک رشته مفروض بعد از عمل مرتب سازی الفبایی Suffix هاست.

به عنوان مثال Suffix Array برای رشته  $banana به صورت زیر است :

2 4 0 1 3 5 6

همانطور که مشاهده می کنید برای یک رشته با n کاراکتر Suffix Array آرایه ای عددی با n خانه است ، به عبارتی پیچیدگی حافظه این ساختمان داده به صورت زیر است :

O(n)

چون این ساختمان داده در مسائل مرتبط با رشته ها (String) و مسائل مرتبط با ژنتیک و بایو و ... به کار برده می شود پیچیدگی حافظه در آن حائز اهمیت است.

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

با چه پیچیدگی زمانی می توان Suffix Array را ایجاد کرد؟

ساده ترین راه ساخت Suffix Array این است که Suffix ها را مرتب کنیم ، اگر از یک الگوریتم مرتب سازی با مرتبه nlogn استفاده کنیم چون در هر بار مقایسه دو رشته با هم مقایسه می شوند (و نه دو عدد) و مقایسه دو رشته از مرتبه n خواهد بود لذا پیچیدگی نهایی این روش از مرتبه n^2logn خواهد بود که به هیچ وجه خوب نیست (در حقیقت اصلاً از این روش برای تولید Suffix Array استفاده نمی شود و این روش فقط برای توضیح مفهوم Suffix Arrray خوب است).

روش دیگر استفاده از Skew Algorithm است که الگوریتم چندان پیچیده ای نیست و مرتبه اجرایی آن اوی n است ، شاید بعداً این الگوریتم را توضیح دادم.یک توضیح خیلی آسان و راحت در مورد این الگوریتم را می توانید از این لینک مشاهده کنید.

روش دیگر که بسیار شبیه روش اول است که کمی ابتکار به آن اضافه شده روش مبتنی بر Bucket Sorting است که در مقاله اصلی نیز از همین روش استفاده شده است ، اگر از یک الگوریتم مرتب سازی مرتبه nlogn استفاده شود پیچیدگی این روش از مرتبه nlog^2n خواهد بود و اگر از یک روش مرتب سازی مانند Radix Sort استفاده شود پیچیدگی این روش از مرتبه nlogn خواهد بود که برای بسیاری از کاربرد ها همین روش کفایت می کند.این روش را می توانید در مقاله اصلی که در ابتدا به آن اشاره شده مطالعه کنید، در اینجا نیز در ادامه کمی در مورد این روش توضیح خواهم داد.

روش دیگر این است که ابتدا Suffix Tree بسازیم که چنین عملی با الگوریتم هایی مانند Ukkonen's Algorithm در مرتبه n قابل اجراست ، تبدیل Suffix Tree به Suffix Array  را نیز می توانی در زمانی از مرتبه  n انجام داد یعنی در نهایت استفاده از این روش از مرتبه n خواهد بود ، با این وجود به چند دلیل در عمل از این روش استفاده چندانی نمی شود، یک : ساخت Suffix Tree حافظه بیشتری می برد و از لحاظ پیچیدگی حافظه این روش بهینه نیست ، دو : ضرایب پنهان در ساخت Suffix Tree معمولاً بزرگ هستند و مرتبه n آن ها چندان بهینه نیست .

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

حل چند مسئله با Suffix Array

با فرض اینکه روشی برای ساخت Suffix Array داشته باشیم (یعنی در حال حاضر نگران پیاده سازی آن نباشیم) ، مسائل متنوعی را می توانیم با S.A حل کنیم که در ادامه چند مورد را خواهیم دید.

یکی از مهم ترین مسائل در زمینه رشته ها پیدا کردن یک رشته W به طول m در رشته S به طول n است. به عنوان مثال فرض کنید می خواهید به دنبال کلمه افراسیاب در کتاب شاهنامه بگردید در اینجا افراسیاب برابر W و شاهنامه برابر با S خواهد ، اگر از الگوریتم های استاندارد Pattern Matching مانند KMP استفاده کنید می توانید این مسئله را در زمان n+m حل کنید ، اگر چه این زمان اجرا در بسیاری از کاربرد ها عالی است ولی اگر قصد طراحی یک موتور جست جوی متن را داشته باشید آنگاه هنگامی که k نفر در سایت شما جست و جو کنند زمان اجرای کل برای همه این k نفر برابر خواهد بود با :

O((n+m)*k)

ولی با استفاده از S.A می توانیم مسئله پیدا کردن رشته W با طول m در رشته بزرگ S با طول n را در زمان mlogn حل کنیم.هنگامی که k نفر این عمل را انجام دهند زمان اجرای کل برابر خواهد بود با :

O(k*(mlogn))

به عنوان مثال فرض کنید k برابر با صد هزار باشد در چنین حالتی روش اول منجر به ضرب طول شاهنامه n در صد هزار خواهد شد که بسیییار عدد بزرگی است ، در صورتی که در روش دوم ضرب صد هزار در لگاریتم طول شاهنامه چندان عدد بزرگی نیست ، m نیز معمولاً چندان بزرگ نیست.

چگونه با استفاده از S.A این مسئله را حل کنیم؟

جواب ساده است. اگر رشته W زیر رشته رشته S باشد آنگاه W باید پیشوندِ (Prefix) یکی از پسوند (Suffix) های رشته S باشد.لذا اگر S.A را برای رشته S داشته باشیم کافی است رشته W را با Suffix های S مقایسه کنیم ، چون Suffix ها در Suffix Array مرتب شده هستند برای عمل مقایسه و جست و جو می توانیم از الگوریتم جست جوی دودویی Binary Search استفاده کنیم.برای یک رشته به طول n عمل جست جوی دو دویی مرتبه logn خواهد داشت ، چون در هر گام جست و جو حداکثر m مقایسه داریم پس پیچیدگی نهایی از مرتبه mlogn خواهد بود.

مثال زیر نشان می دهد که چگونه رشته ra را در رشته abracadabra پیدا می کنیم :

 

الگوریتم ارائه شده برای این روش :

در شبه کد فوق عملگر های < و  => عملگر های مقایسه رشته هستند (مانند compareTo) که رشته W را با Suffix مورد نظر مقایسه می کنند. آرایه Pos همان Suffix Array ساخته شه از رشته اصلی است.

کد زیر پیاده سازی این روش را در جاوا نشان می دهد :



	String S;
	int Pos[];//suffix array
	int N;//S.length()
	String A(int index){
		return S.substring(index);
	}
	
	int Search(String W){
		if(W.compareTo(A(Pos[0]))<=0)
			return 0;
		if(W.compareTo(A(Pos[N-1]))>0)
			return N;
		int L=0,R=N-1;
		while((R-L)>1){
			int M=(R+L)/2;
			if(W.compareTo(A(Pos[M]))<=0){
				R=M;
			}else{
				L=M;
			}
		}
		return R;
	}

در کد فوق فرض می شود که آرایه Pos یعنی Suffix Array رشته S قبلاً حساب شده باشد.

جالب است بدانید که Manber و Myers نشان دادند با کمی اطلاعات اضافی و ساخت آرایه LCP (در اینجا توضیح نخواهم داد) می توان الگوریتم فوق را بهبود داد و مسئله پیدا کردن رشته W به طول m در رشته S به طول n را می توان در زمان m+logn حل کرد.Abouelhoda, Kurtz & Ohlebusch در مقاله ای با عنوان Replacing suffix trees with enhanced suffix arrays از این نیز فراتر رفته اند و نشان دادند که مسئله فوق را می توان در زمان اوی m حل کرد.

البته مسئله فوق را با استفاده از Suffix Tree نیز می توان در زمان اوی m حل کرد.

 

اما مسائل بیشتری وجود دارند که در اینجا به شرح آن ها نمی پردازم و ارجاع می دهم :

پس از اینکه توانستید خودتان Suffix Array را پیاد سازی کنید می توانید پیاده سازی خود را در سوال زیر بسنجید :

http://www.spoj.com/problems/SARRAY

سوالات بیشتری در آدرس زیر اشاره شده اند :

http://www.quora.com/What-are-some-of-the-good-sources-to-understand-suf...

اگر ای سی امی هستید و دنبال کد کوتاه و سریع هستید Suffix Array - a programming contest approach می تواند برای شما مفید باشد.در این مقاله هم پیاده سازی کوتاهی از S.A ارائه شده است و هم مسائل مختلفی مطرح شده است  و نشان داده شده که با S.A قابل حل هستند.

روش معمولی

در ابتدا اشاره کردم که ساده ترین روش مرتب سازی Suffix هاست ، اگرچه این روش در عمل هیچ کارایی ندارد ولی برای شروع و مطالعه بر روی Suffix Array خالی از لطف نیست. کد جاوای زیر پیاده سازی این روش را نشان میدهد :


import java.util.Arrays;


public class SuffixArrayNaiveApproach {
	String S;
	int Pos[];
	int N;
	class Suffix implements Comparable<Suffix>{
		String suffix;
		int index;
		public int compareTo(Suffix other) {
			return suffix.compareTo(other.suffix);
		}
	}
	public SuffixArrayNaiveApproach(String text){
		this.S=text;
		N=S.length();
		Pos=new int[N];
	}
	void createSuffixArray(){
		Suffix suffixes[]=new Suffix[N];
		for(int i=0;i<N;i++){
			suffixes[i]=new Suffix();
			suffixes[i].suffix=S.substring(i);
			suffixes[i].index=i;
		}
		
		Arrays.sort(suffixes);
		
		for(int i=0;i<N;i++){
			Pos[i]=suffixes[i].index;
		}
	}
	void print(){
		for(int i=0;i<N;i++){
			System.out.println(Pos[i]+" : "+S.substring(Pos[i]));
		}
	}
	
	public static void main(String[] args) {
		SuffixArrayNaiveApproach sana=new SuffixArrayNaiveApproach("abracadabra");
		sana.createSuffixArray();
		sana.print();
	}
}


Bucket Sorting

در پایان می خواستم کمی در مورد Bucket Sorting و ابتکار به کار رفته آن صحبت کنم ، اینکه چگونه با یک ابتکار بسیار جالب می توان الگوریتم ناکارای معمولی فوق را به الگوریتمی خیلی خوب از مرتبه nlog^2n تبدیل کرد که فعلاً از حوصله من خارج شده و این موضوع را به آموزش دیگری موکول می کنیم.

 

 

افزودن دیدگاه جدید

Plain text

  • تگ‌های HTML مجاز نیستند.
  • نشانی صفحه‌ها وب و پست الکترونیک بصورت خودکار به پیوند تبدیل می‌شوند.
  • خطوط و پاراگراف‌ها بطور خودکار اعمال می‌شوند.