پوشش پیشوند
دنباله‌کاوی یکی از مسائل مهم و با استفاده‌های گسترده در داده‌کاوی است. دنباله‌کاوی به این دلیل مسئله دشواری است که برای آن نیاز داریم تعداد زیادی زیردنباله تولید کنیم و آن‌ها را آزمایش کنیم. تعداد زیادی از الگوریتم‌های دنباله‌کاوی مانند الگوریتم آپریوری از یک روش ساخت کاندید و آزمایش استفاده می‌کنند اما این روش برای پایگاه‌داده‌های شامل الگوهای متعدد یا زیاد مناسب و بهینه نیست.
پوشش پیشوند یک الگوریتم بهینه برای انجام دنباله‌کاوی است. پوشش پیشوند یک الگوریتم تصویر محور است که از روش گسترش الگو استفاده می‌کند. در این الگوریتم بصورت بازگشتی یک پایگاه‌داده به تعدادی پایگاه‌داده تصویرشده کوچکتر تبدیل می‌شود و الگوها برای هر پایگاه‌داده گسترش می‌یابند و برای هر کدام از پایگاه‌داده‌های کوچکتر الگوهای پرتکرار پیدا می‌شوند.
formula_1 مجموعه آیتم‌ها است. یک مجموعه‌آیتم زیرمجموعه‌ای از مجموعه formula_2 است. دنباله یک دنباله از مجموعه‌آیتم‌ها مانند formula_3 است که هرکدام از formula_4ها یک مجموعه‌آیتم هستند. به هرکدام از formula_4ها یک عضو از دنباله می‌گوییم که به‌صورت formula_6 است که هرکدام از formula_7ها یک آیتم هستند.
به دنباله formula_8 زیردنباله‌ای از formula_9 می‌گوییم اگر formula_10 موجود باشد که برای هر formula_11 مجموعه‌آیتم formula_12 زیرمجموعه‌ای از formula_13 باشد و آنرا با علامت formula_14 نشان می‌دهیم.
اگر S مجموعه‌ای از دنباله‌ها باشد تعریف می‌کنیم:
formula_15
دنباله‌کاوی عددی به عنوان minSupport و مجموعه‌ای مانند S از دنباله‌ها دریافت می‌کند و همه دنباله‌های formula_16 را می‌یابد که:
formula_17 اگر minSupport برابر ۲ باشد و اعضای S بترتیب formula_18 و formula_19 و formula_20 باشد. دنباله formula_18 شامل پنج عضو (a) و (abc) و (ac) و (d) و (cf) است که هرکدام یک مجموعه‌آیتم هستند.
در اینصورت formula_22 یک دنباله جواب است چون زیردنباله‌ای از دنباله‌های اول و سوم S است.
در ابتدا فرض می‌کنیم همه آیتم‌های آیتم‌مجموعه‌ها بصورت مرتب شده هستند. به دنباله formula_23 یک پیشوند از دنباله formula_24 می‌گوییم اگر برای هر formula_25 داشته باشیم formula_26 و formula_27 و همچنین آیتم‌های formula_28 همگی بصورت الفبایی بعد از آیتم‌های formula_29 باشند.
اگر formula_30 زیردنباله‌ای از formula_16 باشد تصویر formula_16 با پیشوند formula_30 زیردنباله formula_34 از formula_16 با شرایط زیر است:
اگر formula_42 پیشوندی از formula_43 باشد به دنباله formula_44 پسوند formula_16 نسبت به formula_30 می‌گوییم که formula_47.
به عنوان مثال formula_48 پیشوندی از formula_49 است و پسوند مربوط به آن formula_50 است.
الگوریتم از این گذاره استفاده می‌کند که اگر formula_51 الگوهای پرتکرار با طول i باشند الگوهای به طول i + 1 را می‌توان به n دسته تقسیم کرد که اعضای دسته jام همگی دارای پیشوند formula_52 باشند. با استفاده از گزاره قبل الگوریتم از سه مرحله تشکیل شده‌است:
Algorithm (PrefixSpan) Prefix-projected sequential pattern mining فرض کنید مجموعه دنباله‌ها بصورت زیر باشد:
formula_74
و مقدار min_support برابر ۲ باشد. ابتدا دنباله‌های پرتکرار با طول ۱ را می‌یابیم که بوضوح با در نظر گرفتن تکرار آیتم‌ها ۴ دنباله formula_75 قابل قبول هستند. حال باید پایگاه‌داده تصویرشده formula_76 را پیدا کنیم که چون formula_76 زیردنباله‌ای از سه دنباله هست پایگاه‌داده بصورت زیر می‌شود.
formula_78
حال با در نظر گرفتن آیتم‌هایی که حداقل دوبار در formula_79 تکرار شده‌اند در این مرحله دو دنباله به طول دو formula_80 پیدا می‌شود. با ادامه انجام این روند همه الگوهای پرتکرار یافت می‌شوند:
frequent_patterns = formula_81
اگر اندازه پایگاه داده های ساخته‌شده کوچک شود به افزایش کارایی الگوریتم کمک می‌کند. به این منظور هنگام ساخت هر پایگاه‌داده تصویری از یک هرس داده‌ها با استفاده از بررسی‌های الگوریتم آپریوری استفاده می‌کنیم. به این روش تصویر دولایه(bi level projection) می‌گویند.
آزمایش‌ها نشان داده‌است که بیشتر هزینه این الگوریتم صرف ساخت پایگاه‌داده‌ها می‌شود و اگر اندازه پایگاه داده بزرگ باشد لازم است تعداد زیادی پایگاه‌داده تصویری تولید شود که هزینه زیادی دارد. به این منظور بجای ساخت فیزیکی پایگاه‌داده‌ها برای هر دنباله یک شماره در نظر می‌گیریم و در هر پایگاه‌داده تنها شماره دنباله‌ها و اندیس مکان شروع پسوند را نگه می‌داریم که باعث افزایش کارایی الگوریتم می‌شود.به این روش شبه تصویر(pseudo projction) می‌گویند.