ماشین غیرمدور قطعی متناهی: تفاوت میان نسخه‌ها

از ویکی‌پدیا، دانشنامهٔ آزاد
نمایش تاریخچه به صورت تعاملی
→ تفاوت قدیمی‌ترتفاوت جدیدتر ←
محتوای حذف‌شده محتوای افزوده‌شده
دیداریویکی‌متن
افزودن {{ویکی‌سازی}} (توینکل)
ابرابزار
خط ۳: خط ۳:
{{بهبود منبع|تاریخ=ژوئن ۲۰۱۵}}
{{بهبود منبع|تاریخ=ژوئن ۲۰۱۵}}
{{تمیزکاری|دلیل=مقاله ضعیف است|تاریخ=ژوئن ۲۰۱۵}}
{{تمیزکاری|دلیل=مقاله ضعیف است|تاریخ=ژوئن ۲۰۱۵}}
در علوم رایانه، یک ماشین غیر مدور قطعی متناهی، (DAFSA)، [1] یا یک گراف جهت دار بدون دور از کلمات(DAWG، هر چند که این نام به ساختمان داده مربوط به توابع به عنوان شاخص پسوند هم اشاره میکند[2]) یک ساختارداده است که نشان دهنده مجموعه ای از رشته هاست، و اجازه می دهد تا برای یک عملیات پرس و جو که امتحان کند که آیا یک رشته داده شده متعلق به مجموعه در زمان متناسب با طول آن هست یا نه. از این جهات، DAFSA بسیار شبیه به یک درخت پیشوندی است، اما با فضای بسیار کارآمد ترو به صرفه تر.
در علوم رایانه، یک ماشین غیر مدور قطعی متناهی، (DAFSA)، یا یک گراف جهت‌دار بدون دور از کلمات(DAWG، هر چند که این نام به ساختمان داده مربوط به توابع به عنوان شاخص پسوند هم اشاره می‌کند) یک ساختارداده است که نشان دهنده مجموعه‌ای از رشته هاست، و اجازه می‌دهد تا برای یک عملیات پرس و جو که امتحان کند که آیا یک رشته داده شده متعلق به مجموعه در زمان متناسب با طول آن هست یا نه. از این جهات، DAFSA بسیار شبیه به یک درخت پیشوندی است، اما با فضای بسیار کارآمد ترو به صرفه تر.


DAFSA یک مورد خاص از یک تشخیص دهنده متناهی است که شبیه به شکل یک گراف بدون دور جهت دار با یک راس مبدا (یک راس با لبه های ورودی)، که در آن هر لبه گراف توسط یک نام و یا نماد برچسب خورده است، که در آن هر راس حداکثر یک لبه خروجی برای هر حرف یا نماد را داراست. رشته های ارائه شده توسط DAFSA از راس مبدا به هر راس سینک یا مقصد (یک راس با هیچ لبه خروجی) با نماد های مشخص شده بر روی هر مسیر در گراف مشخص میشوند. در واقع، یک ماشین قطعی متناهی بدون دور است اگر و تنها اگر آن را یک مجموعه متناهی از رشته به رسمیت می شناسد. [1]
DAFSA یک مورد خاص از یک تشخیص دهنده متناهی است که شبیه به شکل یک گراف بدون دور جهت دار با یک راس مبدأ (یک راس با لبه‌های ورودی)، که در آن هر لبه گراف توسط یک نام و یا نماد برچسب خورده است، که در آن هر راس حداکثر یک لبه خروجی برای هر حرف یا نماد را داراست. رشته‌های ارائه شده توسط DAFSA از راس مبدأ به هر راس سینک یا مقصد (یک راس با هیچ لبه خروجی) با نمادهای مشخص شده بر روی هر مسیر در گراف مشخص می‌شوند. در واقع، یک ماشین قطعی متناهی بدون دور است اگر و تنها اگر آن را یک مجموعه متناهی از رشته به رسمیت می‌شناسد.


مقایسه با درخت پیشوندی
مقایسه با درخت پیشوندی
با فرض اینکه برای رسیدن به یک راس چند مسیر متفاوت وجود داشته باشد، DAFSA ممکن است به طور قابل توجهی راس کمتر از درخت پیشوندی مرتبط برای رسیدن به راس مقصد استفاده کند.به عنوان مثال، برای چهار کلمه انگلیسی "tap", "taps", "top", and "tops". یک درخت پیشوندی با 11 راس وجود خواهد داشت ، یکی برای هر رشته به عنوان یک پیشوند برای این کلمات، و یا برای هر کلمه " پایان رشته " برچسب خورده باشد. با این حال، DAFSA میتواند این چهار کلمه ی مشابه را با استفاده از تنها شش راس vi برای i از 0 تا 5 ، و لبه های زیر نشان دهد :
با فرض اینکه برای رسیدن به یک راس چند مسیر متفاوت وجود داشته باشد، DAFSA ممکن است به طور قابل توجهی راس کمتر از درخت پیشوندی مرتبط برای رسیدن به راس مقصد استفاده کند. به عنوان مثال، برای چهار کلمه انگلیسی "tap", "taps", "top", and "tops". یک درخت پیشوندی با ۱۱ راس وجود خواهد داشت، یکی برای هر رشته به عنوان یک پیشوند برای این کلمات، و یا برای هر کلمه " پایان رشته " برچسب خورده باشد. با این حال، DAFSA می‌تواند این چهار کلمهٔ مشابه را با استفاده از تنها شش راس vi برای i از ۰ تا ۵، و لبه‌های زیر نشان دهد:
⚫
یک لبه از V0 به V1 با برچسب "T"، دو لبه از V1 تا V2 با برچسب "A" و " O "، یک لبه از V2 به V3 با برچسب" p "، یک لبه از V3به V4 با برچسب" S "، و لبه هایی از V3 و V4 به V5 با برچسب " پایان رشته ". یک مقایسه بین حافظه و قابلیت وجود دارد، زیرا یک DAFSA استاندارد می تواند بگوید که یک کلمه در آن وجود دارد یا نه، اما نمی توانداطلاعات اضافه ای در مورد آن بدهد، در حالی که یک درخت پیشوندی چنین قابلیتی را داراست.


⚫
یک لبه از V0 به V1 با برچسب "T"، دو لبه از V1 تا V2 با برچسب "A" و " O "، یک لبه از V2 به V3 با برچسب" p "، یک لبه از V3به V4 با برچسب" S "، و لبه‌هایی از V3 و V4 به V5 با برچسب " پایان رشته ". یک مقایسه بین حافظه و قابلیت وجود دارد، زیرا یک DAFSA استاندارد می‌تواند بگوید که یک کلمه در آن وجود دارد یا نه، اما نمی‌توانداطلاعات اضافه‌ای در مورد آن بدهد، در حالی که یک درخت پیشوندی چنین قابلیتی را داراست.
⚫
تفاوت اصلی بین DAFSA و درخت پیشوندی حذف افزونگی پسوند و میانوند در ذخیره سازی رشته است.درخت پیشوندی به حذف افزونگی پیشوند از همه پیشوندها مشترک بین رشته ها میپردازد، مانند پزشکان و دکترای که پیشوند دکتر مشترک است. در یک DAFSA پسوند مشترک نیز به اشتراک گذاشته میشود، برای کلماتی که مجموعه ای از پسوند های یکسان برای دیگر دارند. برای مجموعه فرهنگ لغت از کلمات انگلیسی رایج، این روش، باعث کاهش استفاده ازحافظه در هنگام ترجمه میشود.
⚫
از آنجا که می توان با چندین مسیر به یک گره پایانی در DAFSAرسید ،DAFSA به طور مستقیم نمی تواند اطلاعات کمکی و اضافی مربوط به هر مسیر را ذخیره کند ، به عنوان مثال تکرار یک کلمه در زبان انگلیسی.با این حال، اگر برای هر گره ما تعداد مسیرهای منحصر به فرد از طریق آن نقطه در ساختار را ذخیره کنیم، می توانیم آن را به بازیابی شاخص از یک کلمه، یا یک کلمه با توجه به شاخص آن استفاده کنید. [3] در آن صورت اطلاعات کمکی می تواند در یک آرایه ذخیره می شود.


⚫
تفاوت اصلی بین DAFSA و درخت پیشوندی حذف افزونگی پسوند و میانوند در ذخیره‌سازی رشته است. درخت پیشوندی به حذف افزونگی پیشوند از همه پیشوندها مشترک بین رشته‌ها می‌پردازد، مانند پزشکان و دکترای که پیشوند دکتر مشترک است. در یک DAFSA پسوند مشترک نیز به اشتراک گذاشته می‌شود، برای کلماتی که مجموعه‌ای از پسوندهای یکسان برای دیگر دارند. برای مجموعه فرهنگ لغت از کلمات انگلیسی رایج، این روش، باعث کاهش استفاده ازحافظه در هنگام ترجمه می‌شود.
⚫
منابع :

References[edit]
⚫
از آنجا که می‌توان با چندین مسیر به یک گره پایانی در DAFSAرسید ،DAFSA به طور مستقیم نمی‌تواند اطلاعات کمکی و اضافی مربوط به هر مسیر را ذخیره کند، به عنوان مثال تکرار یک کلمه در زبان انگلیسی. با این حال، اگر برای هر گره ما تعداد مسیرهای منحصر به فرد از طریق آن نقطه در ساختار را ذخیره کنیم، می‌توانیم آن را به بازیابی شاخص از یک کلمه، یا یک کلمه با توجه به شاخص آن استفاده کنید. در آن صورت اطلاعات کمکی می‌تواند در یک آرایه ذخیره می‌شود.
^ Jump up to: a b Jan Daciuk, Stoyan Mihov, Bruce Watson and Richard Watson (2000). Incremental construction of minimal acyclic finite state automata. Computational Linguistics 26(1):3-16.

Jump up ^ Black, Paul E. "directed acyclic word graph". Dictionary of Algorithms and Data Structures. NIST.
⚫
== منابع ==
Jump up ^ Kowaltowski, T.; CL Lucchesi (1993). "Applications of finite automata representing large vocabularies". Software-Practice and Experience 1993: 15–30. CiteSeerX: 10.1.1.56.5272.
{{پانویس}}
Blumer, A.; Blumer, J.; Haussler, D.; Ehrenfeucht, A.; Chen, M.T.; Seiferas, J. (1985), "The smallest automation recognizing the subwords of a text", Theoretical computer science 40: 31–55, doi:10.1016/0304-3975(85)90157-4
* {{citation | last1=Blumer | first1=A. | last2=Blumer | first2=J. | last3=Haussler | first3=D. | last4=Ehrenfeucht | first4=A. | last5=Chen | first5=M.T. | last6=Seiferas | first6=J.| title=The smallest automation recognizing the subwords of a text | year=1985 | journal=Theoretical computer science | pages=31–55 | volume=40 | doi=10.1016/0304-3975(85)90157-4}}
Appel, Andrew; Jacobsen, Guy (1988), "The World's Fastest Scrabble Program" (PDF), Communications of the ACM. One of the early mentions of the data structure.
* {{citation | first1=Andrew | last1=Appel | first2=Guy | last2=Jacobsen | title= The World's Fastest Scrabble Program | year=1988 | journal=Communications of the ACM | url=http://www.cs.cmu.edu/afs/cs/academic/class/15451-s06/www/lectures/scrabble.pdf | format=PDF}}. One of the early mentions of the data structure.
Jansen, Cees J. A.; Boekee, Dick E. (1990), "On the significance of the directed acyclic word graph in cryptology", Advances in Cryptology — AUSCRYPT '90, Lecture Notes in Computer Science 453, Springer-Verlag, pp. 318–326, doi:10.1007/BFb0030372, ISBN 3-540-53000-2.
* {{citation | first1=Cees J. A. | last1=Jansen | first2=Dick E. | last2=Boekee | contribution=On the significance of the directed acyclic word graph in cryptology | series=Lecture Notes in Computer Science | publisher=[[اشپرینگر ساینس+بیزینس مدیا]] | title=Advances in Cryptology — AUSCRYPT '90 | volume=453 | pages=318–326 | doi=10.1007/BFb0030372 | year=1990 | isbn=3-540-53000-2}}.
Epifanio, Chiara; Mignosi, Filippo; Shallit, Jeffrey; Venturini, Ilaria (2004), "Sturmian graphs and a conjecture of Moser", in Calude, Cristian S.; Calude, Elena; Dineen, Michael J., Developments in language theory. Proceedings, 8th international conference (DLT 2004), Auckland, New Zealand, December 2004, Lecture Notes in Computer Science 3340, Springer-Verlag, pp. 175–187, ISBN 3-540-24014-4, Zbl 1117.68454
* {{citation | last1=Epifanio | first1=Chiara | last2=Mignosi | first2=Filippo | last3=Shallit | first3=Jeffrey | last4=Venturini | first4=Ilaria | chapter=Sturmian graphs and a conjecture of Moser | pages=175–187 | editor1-last=Calude | editor1-first=Cristian S. | editor2-last=Calude | editor2-first=Elena | editor3-last=Dineen | editor3-first=Michael J. | title=Developments in language theory. Proceedings, 8th international conference (DLT 2004), Auckland, New Zealand, December 2004 | year=2004 | publisher=[[اشپرینگر ساینس+بیزینس مدیا]] | series=Lecture Notes in Computer Science | volume=3340 | isbn=3-540-24014-4 | zbl=۱۱۱۷٫۶۸۴۵۴}}

== پیوند به بیرون ==
* [http://pages.pathcom.com/~vadco/dawg.html http://pages.pathcom.com/~vadco/dawg.html] - JohnPaul Adamovsky teaches how to construct a DAFSA using an array of integers.
* [http://pages.pathcom.com/~vadco/cwg.html http://pages.pathcom.com/~vadco/cwg.html] - JohnPaul Adamovsky teaches how to construct a DAFSA hash function using a novel encoding with multiple integer arrays. This encoding is called the Caroline Word Graph (CWG).

{{ساختمان داده‌ها}}

نسخهٔ ‏۳۰ ژوئن ۲۰۱۵، ساعت ۱۹:۴۵

در علوم رایانه، یک ماشین غیر مدور قطعی متناهی، (DAFSA)، یا یک گراف جهت‌دار بدون دور از کلمات(DAWG، هر چند که این نام به ساختمان داده مربوط به توابع به عنوان شاخص پسوند هم اشاره می‌کند) یک ساختارداده است که نشان دهنده مجموعه‌ای از رشته هاست، و اجازه می‌دهد تا برای یک عملیات پرس و جو که امتحان کند که آیا یک رشته داده شده متعلق به مجموعه در زمان متناسب با طول آن هست یا نه. از این جهات، DAFSA بسیار شبیه به یک درخت پیشوندی است، اما با فضای بسیار کارآمد ترو به صرفه تر.

DAFSA یک مورد خاص از یک تشخیص دهنده متناهی است که شبیه به شکل یک گراف بدون دور جهت دار با یک راس مبدأ (یک راس با لبه‌های ورودی)، که در آن هر لبه گراف توسط یک نام و یا نماد برچسب خورده است، که در آن هر راس حداکثر یک لبه خروجی برای هر حرف یا نماد را داراست. رشته‌های ارائه شده توسط DAFSA از راس مبدأ به هر راس سینک یا مقصد (یک راس با هیچ لبه خروجی) با نمادهای مشخص شده بر روی هر مسیر در گراف مشخص می‌شوند. در واقع، یک ماشین قطعی متناهی بدون دور است اگر و تنها اگر آن را یک مجموعه متناهی از رشته به رسمیت می‌شناسد.

مقایسه با درخت پیشوندی با فرض اینکه برای رسیدن به یک راس چند مسیر متفاوت وجود داشته باشد، DAFSA ممکن است به طور قابل توجهی راس کمتر از درخت پیشوندی مرتبط برای رسیدن به راس مقصد استفاده کند. به عنوان مثال، برای چهار کلمه انگلیسی "tap", "taps", "top", and "tops". یک درخت پیشوندی با ۱۱ راس وجود خواهد داشت، یکی برای هر رشته به عنوان یک پیشوند برای این کلمات، و یا برای هر کلمه " پایان رشته " برچسب خورده باشد. با این حال، DAFSA می‌تواند این چهار کلمهٔ مشابه را با استفاده از تنها شش راس vi برای i از ۰ تا ۵، و لبه‌های زیر نشان دهد:

یک لبه از V0 به V1 با برچسب "T"، دو لبه از V1 تا V2 با برچسب "A" و " O "، یک لبه از V2 به V3 با برچسب" p "، یک لبه از V3به V4 با برچسب" S "، و لبه‌هایی از V3 و V4 به V5 با برچسب " پایان رشته ". یک مقایسه بین حافظه و قابلیت وجود دارد، زیرا یک DAFSA استاندارد می‌تواند بگوید که یک کلمه در آن وجود دارد یا نه، اما نمی‌توانداطلاعات اضافه‌ای در مورد آن بدهد، در حالی که یک درخت پیشوندی چنین قابلیتی را داراست.

تفاوت اصلی بین DAFSA و درخت پیشوندی حذف افزونگی پسوند و میانوند در ذخیره‌سازی رشته است. درخت پیشوندی به حذف افزونگی پیشوند از همه پیشوندها مشترک بین رشته‌ها می‌پردازد، مانند پزشکان و دکترای که پیشوند دکتر مشترک است. در یک DAFSA پسوند مشترک نیز به اشتراک گذاشته می‌شود، برای کلماتی که مجموعه‌ای از پسوندهای یکسان برای دیگر دارند. برای مجموعه فرهنگ لغت از کلمات انگلیسی رایج، این روش، باعث کاهش استفاده ازحافظه در هنگام ترجمه می‌شود.

از آنجا که می‌توان با چندین مسیر به یک گره پایانی در DAFSAرسید ،DAFSA به طور مستقیم نمی‌تواند اطلاعات کمکی و اضافی مربوط به هر مسیر را ذخیره کند، به عنوان مثال تکرار یک کلمه در زبان انگلیسی. با این حال، اگر برای هر گره ما تعداد مسیرهای منحصر به فرد از طریق آن نقطه در ساختار را ذخیره کنیم، می‌توانیم آن را به بازیابی شاخص از یک کلمه، یا یک کلمه با توجه به شاخص آن استفاده کنید. در آن صورت اطلاعات کمکی می‌تواند در یک آرایه ذخیره می‌شود.

منابع

  • Blumer, A.; Blumer, J.; Haussler, D.; Ehrenfeucht, A.; Chen, M.T.; Seiferas, J. (1985), "The smallest automation recognizing the subwords of a text", Theoretical computer science, 40: 31–55, doi:10.1016/0304-3975(85)90157-4
  • Appel, Andrew; Jacobsen, Guy (1988), "The World's Fastest Scrabble Program" (PDF), Communications of the ACM. One of the early mentions of the data structure.
  • Jansen, Cees J. A.; Boekee, Dick E. (1990), "On the significance of the directed acyclic word graph in cryptology", Advances in Cryptology — AUSCRYPT '90, Lecture Notes in Computer Science, vol. 453, اشپرینگر ساینس+بیزینس مدیا, pp. 318–326, doi:10.1007/BFb0030372, ISBN 3-540-53000-2.
  • Epifanio, Chiara; Mignosi, Filippo; Shallit, Jeffrey; Venturini, Ilaria (2004), "Sturmian graphs and a conjecture of Moser", in Calude, Cristian S.; Calude, Elena; Dineen, Michael J. (eds.), Developments in language theory. Proceedings, 8th international conference (DLT 2004), Auckland, New Zealand, December 2004, Lecture Notes in Computer Science, vol. 3340, اشپرینگر ساینس+بیزینس مدیا, pp. 175–187, ISBN 3-540-24014-4, Zbl ۱۱۱۷٫۶۸۴۵۴ {{citation}}: Check |zbl= value (help)

پیوند به بیرون

برگرفته از «https://fa.wikipedia.org/w/index.php?title=ماشین_غیرمدور_قطعی_متناهی&oldid=15462695»