קבוצות אטומיות בביטויים רגולאריים

01/11/2022

אחד השינויים המעניינים שתמצאו ברשימת החידושים של פייתון 11 נקרא Regular Expressions Atomic Grouping. מסתבר שמאחורי השם המפוצץ מסתתר תחביר פשוט וחמוד, שאפילו יכול להציל את המערכת שלכם מהתרסקות אטומית.

אחת הבעיות עם ביטויים רגולאריים נקראת Catastrophic Backtracking. קחו לדוגמה את הביטוי הרגולארי:

re = /W(X|Y+)+Z/

ואת הטקסט:

text = "WYYYYYYYYYYYYYYYYYYYYYYYYYYYYA"

כשתבקשו מרובי (או כל מפענח אחר) לבדוק אם הטקסט מתאים לביטוי הרגולארי תופתעו לראות שלמרות ששום דבר פה לא ארוך במיוחד, זה לוקח כמה שניות טובות עד שמקבלים תשובה. הסיבה היא שמנוע הביטויים הרגולאריים כל הזמן חוזר ומנסה עוד ועוד אפשרויות מתוך הקבוצה X|Y+, ועל כל אפשרות מנסה עוד ועוד אפשרויות לכמה פעמים הקבוצה תופיע.

סימון קבוצה בתור קבוצה אטומית אומר למנוע הביטויים הרגולאריים לא לחזור לחפש התאמות מאותה קבוצה אחרי שכבר בחרנו ממנה איזושהי אפשרות. כלומר פעם אחת נכנסת ולקחת את כל ה Y-ים שיתאימו ל Y שבתוך הקבוצה, וזהו זה מה שיש. מפה אתה לא נכנס שוב לקבוצה הזאת ומנסה מספר אחר של Y-ים שיתאימו. הצליח? יופי, לא הצליח? מנתקים.

בשביל להגדיר קבוצה אטומטית אנחנו כותבים בתוך הסוגריים סימן שאלה ואחריו סימן גדול-מ ואז את התוכן, במקרה שלנו הביטוי הרגולארי יהיה:

re = /W(?>X|Y+)+Z/

ניסיון להתאים ביטוי כזה על הטקסט ייכשל מיד, מה שעשוי להציל את השרת אם הקלט גדול ומכוון להזיק.

שימו לב ששינוי קבוצה לקבוצה אטומית משנה את המשמעות של הביטוי. לדוגמה הביטוי הזה:

re = /a(bc|b)c/

יתאים לטקסטים abc ו abcc, אבל אם אני הופך את הקבוצה לאטומית והאופציה של bc תיכשל, המנוע לא יחזור לנסות את b ולכן הטקסט abc לא יתאים לביטוי a(?>bc|b)c. בסך הכל קבוצות אטומיות הן כלי מתקדם שחשוב להכיר אם אתם משתמשים בביטויים רגולאריים על קלט לא מפולטר ורוצים לוודא שקלט זדוני לא שובר לכם את השרת. והחל מפייתון 3.11 תוכלו להשתמש בהן גם בפייתון.