איחוד קבוצות זרות

במדעי המחשב, איחוד קבוצות זרות (באנגלית: Disjoint-Set Data Structure), הוא מבנה נתונים אשר מבצע מעקב אחרי קבוצה של עצמים המחולקים למספר של תתי-קבוצות זרות ולא חופפות.

לאחר הפעלת יצירה 8 פעמים, ייווצרו 8 יחידונים.

אחרי כמה הפעלות של איחוד, חלק מהקבוצות התאגדו יחדיו.

אלגוריתם איחוד-חיפוש (באנגלית: Union-Find Algorithm), הוא אלגוריתם המבצע את שתי הפעולות השימושיות הבאות על מבנה נתונים זה:

• חיפוש (Find): קביעה איזו קבוצה מכילה עצם ספציפי. פעולה זו יכולה גם לעזור בקביעה האם שני עצמים שייכים לאותה הקבוצה.
• איחוד (Union): איחוד שתי קבוצות לכדי קבוצה אחת.

פעולה הכרחית נוספת היא יצירה (MakeSet), פעולה היוצרת קבוצה חדשה המכילה עצם אחד בלבד (סינגלטון).

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

מימוש בעזרת רשימות מקושרות

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

פעולת יצירה תיצור רשימה בעלת איבר אחד. פעולת איחוד תבצע שרשור של שתי רשימות. אולם, בגישה ישירה זו, המימוש של פעולת חיפוש הוא יקר מבחינת סיבוכיות זמן. בעוד שתי הפעולות הראשונות עובדות בסיבוכיות של זמן קבוע, אותה מסמנים בעזרת הסימון האסימפטוטי $O(1)$, פעולה זו תדרוש סיבוכיות ליניארית בגודל הרשימה, $O(n)$. זאת מכיוון שבפעולת חיפוש אנו נאלצים לסרוק רשימה החל מהעצם הנתון ועד לנציג (ראש הרשימה), אותו אנו מתבקשים להחזיר כפלט.

מעקף (Workaround) אפשרי לבעיה זו, הוא תוספת של מצביע לראש הרשימה מכל איבר (Node) ברשימה. בעזרת המצביע, נוכל פשוט לגשת לנציג באופן מיידי, וכך פעולת חיפוש תיעשה בזמן קבוע. לעומת זאת, פעולת איחוד תידרש כעת לדאוג לתחזוקת המצביעים של איברי הרשימה המאוחדת. שהרי, לאחר שרשור שתי רשימות, חלק מהאיברים מחזיקים מצביעים לראש הרשימה הישנה, שאינו רלוונטי יותר כנציג. כתוצאה מכך, פעולת האיחוד תעבוד עתה בסיבוכיות ליניארית. המסקנה היא שהבעיה לא נפתרה, אלא הצגנו שקלול תמורות (Tradeoff) בין סיבוכיות פעולות האיחוד והחיפוש.

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

ניתוח אסימפטוטי

נרצה לנתח באופן אסימפטוטי את סיבוכיות הפעולות על מבנה נתונים הממומש כמתואר לעיל (בעזרת רשימות מקושרות ועם שימוש במצביעים והשוואת אורכים). נראה כי סיבוכיות הזמן של ביצוע $m$ פעולות על פני מבנה נתונים בעל $n$ עצמים נתונה על ידי $O(m+n\log(n))$ זמן.

נניח כי כל איבר ברשימה מקושרת שומר שני שדות: שם הרשימה אליה הוא שייך (מצביע לראש הרשימה) ואת אורכה של הרשימה. בנוסף, נניח כי מספר האיברים הכולל בכל הרשימות הוא $n$ (כלומר, מבנה הנתונים מחזיק בסך הכל $n$ עצמים). כפי שראינו, הפעולה היחידה שאינה עובדת בזמן קבוע היא פעולת איחוד. כזכור, מימשנו פעולה זו בעזרת שרשור רשימות. ברצוננו לאפשר את תחזוקתם של מאפייני הרשימה (שם ואורך) בכל האיברים ברשימה המאוחדת.

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

אם כן, השאלה שנותרה היא "כמה פעמים ניתן להכפיל מספר פי שניים לפני שהוא עובר את הגודל $n$?", שהרי לאחר מכן הרשימה שמכילה את $x$ תכיל $n$ איברים, וכל הפעולות על מבנה הנתונים יעבדו בזמן קבוע. התשובה לשאלה נתונה על ידי לוגריתם בבסיס 2 על מספר האיברים, כלומר בדיוק $\log _{2}(n)$.

המסקנה עד כה, היא שבהינתן עצם כלשהו ניתן לבצע עדכון של שדה שם-הרשימה לכל היותר $\log _{2}(n)$ פעמים במקרה הגרוע ביותר. לכן, עדכון מבנה נתונים בעל $n$ עצמים הממומש בשיטה שתוארה לעיל, ידרוש $O(n\log(n))$ זמן במקרה הגרוע ביותר. כל פעולת חיפוש יכולה להיעשות ב-$O(1)$ זמן עבור מבנה הנתונים מכיוון שכל איבר ברשימה מחזיק שדה הקובע את שם הרשימה ואנו דואגים לעדכן ולתקף שדה זה, לכן פעולות חיפוש או יצירה יעבדו בזמן $O(m)$. בסך הכל נקבל $O(m+n\log(n))$ כרצוי.

תוצאה מעניינת נוספת היא הסיבוכיות המשוערכת של מבנה הנתונים. עבור $n$ פעולות על $n$ עצמים, תתקבל סיבוכיות משוערכת של $O(\log n)$ עבור ביצוע פעולה יחידה.

מימוש בעזרת יער של קבוצות זרות

יער של קבוצות זרות הוא מימוש של מבנה הנתונים בו כל קבוצה מיוצגת בעזרת עץ.

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

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

קטע הקוד הבא הוא פסאודו קוד.

 function MakeSet(x)
     x.parent := x

 function Find(x)
     if x.parent == x
        return x
     else
        return Find(x.parent)

 function Union(x, y)
     xRoot := Find(x)
     yRoot := Find(y)
     xRoot.parent := yRoot

איחוד על פי דרגה

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

עצים בעלי איבר יחיד יוגדרו להיות בעלי דרגה 0, ובכל פעם ששני עצים מדרגה $r$ מאוחדים, דרגת העץ המאוחד תוגדר $r+1$. נשים לב כי עבור עצים מדרגה שונה, דרגת העץ המאוחד תהיה זהה לדרגתו של העץ הגדול מביניהם.

שימוש בטכניקה זו לבדה מניב זמן ריצה של $O(\log n)$ לכל פעולת איחוד או חיפוש על פני מבנה נתונים בעל $n$ עצמים. פסאודו קוד עבור מימוש הפעולות יצירה ואיחוד תחת טכניקה זו מוצג להלן.

קטע הקוד הבא הוא פסאודו קוד.

 function MakeSet(x)
     x.parent := x
     x.rank   := 0

 function Union(x, y)
     xRoot := Find(x)
     yRoot := Find(y)
     if xRoot == yRoot
         return

     // x and y are not already in same set. Merge them.
     if xRoot.rank < yRoot.rank
         xRoot.parent := yRoot
     else if xRoot.rank > yRoot.rank
         yRoot.parent := xRoot
     else
         yRoot.parent := xRoot
         xRoot.rank := xRoot.rank + 1

דחיסת מסלולים

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

קטע הקוד הבא הוא פסאודו קוד.

 function Find(x)
     if x.parent != x
        x.parent := Find(x.parent)
     return x.parent

ניתוח אסימפטוטי משוערך

לוגריתם חוזר

הניתוח המוכר הראשוני של זמן לכל פעולה הוכח על ידי הופקרופט ואולמן בשנת 1973 ונקבע בתור $O(\log ^{*}n)$, הלוגריתם החוזר. נוכיח כי עבור $m$ פעולות של איחוד או חיפוש, המופעלות על מבנה נתונים בעל $n$ עצמים, מתקבל זמן ריצה של $O(m\log ^{*}n)$.

למה 1: דרגת הצמתים לאורך מסלול חיפוש גדלה ממש.

הוכחה: נוכיח את הטענה בעזרת אינדוקציה. בתחילה, כל איבר נמצא בעץ נפרד ($n$ עצים בעלי איבר יחיד). ברור כי הטענה מתקיימת באופן טריוויאלי. המקרה היחיד בו דרגה של צומת משתנה, היא כאשר מבצעים איחוד. כפי שהגדרנו לעיל, העץ בעל הדרגה הקטנה יותר, יחובר אל העץ בעל הדרגה הגדולה יותר. אם דרגות השורשים שנרצה לאחד שוות, אזי אם העצים הם מדרגה $r$, נקבל עץ בעל דרגה $r+1$, שהיא גדולה ממש. במהלך חיפוש, כל הצמתים בהם אנו מבקרים בדרך אל השורש, מחוברים אליו ישירות. מכיוון שלשורש יש דרגה גדולה יותר מכל ילדיו, גם במקרה זה הטענה נשמרת.

למה 2: לעץ בעל שורש עם דרגה $r$ יש לפחות $2^{r}$ איברים (כולל השורש).

הוכחה: בתחילה, כאשר כל איבר הוא השורש של העץ עצמו, הטענה מתקיימת באופן טריוויאלי, מכיוון שדרגת כל השורשים היא $0$ ואכן ישנם בדיוק $1=2^{0}$ צמתים בכל עץ (השורש עצמו בלבד). נניח כי לעץ בעל שורש עם דרגה $r$ יש לפחות $2^{r}$ צמתים בתת-העץ שלו. אז כאשר נבצע איחוד בין שני עצים מדרגה $r$, נקבל עץ בעל דרגה $r+1$, ובו לפחות $2^{r}+2^{r}=2^{r+1}$ איברים. כאשר נבצע איחוד בין שני עצים מדרגות שונות, דרגת השורש לא תשתנה ומספר האיברים בעץ רק יגדל. בכל מקרה, הטענה נשמרת.

למה 3: המספר המרבי של צמתים בעלי דרגה $r$ הוא לכל היותר ${\frac {n}{2^{r}}}$.

הוכחה: כפי שהראינו בעזרת למה 2, אנו יודעים כי בעץ עם שורש מדרגה $r$ יש לפחות $2^{r}$ צמתים. נקבל את המספר המרבי של צמתים מדרגה $r$ כאשר כל איבר מדרגה $r$ יהיה השורש של עץ עם בדיוק $2^{r}$ צמתים (אחרת, ישנם צמתים שהיו יכולים להיות משויכים לעץ אחר ולהגדיל את דרגת השורש שלו). במקרה זה, מספר הצמתים מדרגה $r$ הוא בדיוק ${\frac {n}{2^{r}}}$. אם כן, במקרה הכללי, מספר האיברים יכול להיות רק קטן או שווה לגודל זה.

מטעמי נוחות, נגדיר דלי: דלי הוא קבוצה של צמתים בעלי דרגות.

בהינתן קבוצת עצמים (צמתים), אנו יוצרים דליים וממיינים אליהם צמתים על פי דרגותיהם ועל פי החוקיות הבאה: צמתים בעלי דרגה 0 ישוייכו לדלי שיתוייג ב-0, צמתים בעלי דרגה 1 ישוייכו לדלי שיתוייג ב-1, צמתים בעלי דרגה 2 או 3 ישוייכו לדלי שיתוייג ב-2, ובאופן כללי, צמתים בעלי דרגה בין $B$ לבין $2^{B}-1$ ישוייכו לדלי שיתוייג ב-$B$.

נוכל לבצע שתי אבחנות לגבי הדליים:

1. מספר הדליים המרבי הוא לכל היותר $\log ^{*}n$ (הלוגריתם החוזר).

הוכחה: כאמור, בדלי מספר $B$ ימוקמו הצמתים בעלי דרגות בתחום הסגור $[{B,2^{B}-1}]$. בדלי הבא, ימוקמו הצמתים בעלי הדרגות בתחום הסגור $[{2^{B},2^{2^{B}}-1}]$. אם כן, במעבר מדלי אחד למשנהו, אנו מוסיפים 2 אחד נוסף לחזקה. מספר הדליים שיתקבלו, בהינתן שישנם $n$ צמתים, יהיה אם כן לכל היותר $\log ^{*}n$ על פי הגדרתו.

2. מספר הצמתים בדלי $[{B,2^{B}-1}]$ הוא לכל היותר ${\frac {2n}{2^{B}}}$.

הוכחה: מספר הצמתים המרבי בדלי זה, על פי למה 3: ${\frac {n}{2^{B}}}+{\frac {n}{2^{B+1}}}+{\frac {n}{2^{B+2}}}+\cdots +{\frac {n}{2^{2^{B}-1}}}\leq {\frac {2n}{2^{B}}}$. נעזרנו כאן בסכום של סדרה הנדסית בעלת מנה ${\frac {1}{2}}$. ניגש עתה להוכחת החסם על סיבוכיות זמן הריצה. כזכור, נוכיח כי עבור $m$ פעולות של איחוד או חיפוש, המופעלות על מבנה נתונים בעל $n$ עצמים, מתקבל זמן ריצה של $O(m\log ^{*}n)$.לאחר $m$ פעולות של איחוד או חיפוש ניוותר עם סדרת עצים $\{T_{1},T_{2},...\}$, אשר גודלם $\{n_{1},n_{2},...\}$ בהתאמה, וכן בוצעו עליהם $\{m_{1},m_{2},...\}$ פעולות בהתאמה. ובמילים אחרות, $m_{i}$ פעולות איחוד/חיפוש בוצעו על צמתים של $T_{i}$.

כל צומת מתחיל כקבוצה בפני עצמה, המונה איבר יחיד, ולכן על מנת שהעץ $T_{i}$ יהיה מגודל $n_{i}$, חייבים להפעיל לפחות $n_{i}-1$ פעולות איחוד על העץ, ובפרט $m_{i}\geq n_{i}-1$.

נראה עתה כי לכל עץ $T_{i}$, עלות $m_{i}$ הפעולות שבוצעו בו חסומה על ידי $O({({m_{i}+n_{i}})\log ^{*}n})=O({m_{i}\log ^{*}n})$.

הוכחה: עלות פעולת איחוד היא $O(1)$ ולכן פעולות אלו עולות לכל היותר $O(m_{i})$. עלות פעולת חיפוש היא ליניארית במספר הקשתות על המסלול אל השורש. נחלק קשתות אלו לשלושה סוגים:

1. קשתות בין בן של שורש לבין שורש:

קיימת לכל היותר קשת אחת כזו על כל מסלול חיפוש, מכאן שקשתות מסוג זה תורמות $O(m_{i})$.

2. קשתות בין צומת ואביו, הנמצאים בדליים שונים:

על פי למה 1, בעת עלייה במסלול חיפוש של צומת, אנו רק עולים בדרגה, לכן קשת מסוג 2 תתאים למעבר אל דלי עם דרגות גדולות יותר. המעבר ההפוך, אל דלי בעל דרגות קטנות יותר, אינו אפשרי. על פי אבחנה 1 מספר הדליים הוא לכל היותר $\log ^{*}n$, על כן יהיו לכל היותר $\log ^{*}n$ קשתות מסוג 2. לכן על פני כל הפעולות על קשתות אלו, יתקבל זמן $O({m_{i}\log ^{*}n})$.

3. קשתות בין צומת ואביו, הנמצאים באותו דלי:

נניח כי אנו מסיירים על העץ מצומת $u$ אל צומת $v$, המחוברים ביניהם בעזרת קשת מסוג 3. על פי הגדרת קשת זו, הצמתים שייכים לאותו הדלי. נניח אם כן כי הצמתים הם בעלי דרגה המשויכת לדלי $[{B,2^{B}-1}]$. מכיוון שאנו מבצעים כיווץ מסלולים ומכיוון שלכל צומת יש דרגה גדולה ממש מלכל צאצאיו (על פי למה 1), אזי בכל פעם שבה נעלה בקשת מסוג 3, דרגת האב החדש של $u$ גדלה. למעשה, דרגת האב של $u$ לא יכולה לקטון. מספר הפעמים שדרגת האב של $u$ יכולה לגדול ועדיין הקשת בין $u$ לבין אביו תוגדר כקשת מסוג 3, הוא כגודלו של הדלי. אם כן, נוכל לחצות את הקשת לכל היותר $2^{B}-1-B$ פעמים (בדיוק כגודל הדלי). גודל זה חסום מלמעלה על ידי $2^{B}$. ומכאן נקבל כי מספר הקשתות מסוג 3 הוא $\sum _{[B,2^{B}-1]}\sum _{u}2^{B}$. על פי אבחנה 1 ואבחנה 2, נוכל להסיק כי $\sum _{[B,2^{B}-1]}\sum _{u}2^{B}\leq \sum _{B}2^{B}{\frac {2n}{2^{B}}}\leq 2n\log ^{*}n$. מכאן שקשתות מסוג זה תורמות $O({n_{i}\log ^{*}n})=O({m_{i}\log ^{*}n})$ (מעבר זה נובע מכך ש-$m_{i}\geq n_{i}-1$).

ולסיכום, העלות של $m_{i}$ פעולות על העץ $T_{i}$ מורכבת מהעלות של $O(m_{i})$ בזכות קשתות מסוג 1, $O(m_{i}\log ^{*}n)$ בזכות קשתות מסוג 2 וכן $O(m_{i}\log ^{*}n)$ בזכות קשתות מסוג 3. העלות הכוללת של כלל הפעולות על העץ נתונה על ידי $O(m_{i}\log ^{*}n)$. נסכום מסקנה זו על פני כל העצים במבנה הנתונים, כאשר נזכור כי $m=\sum {m_{i}}$, ונקבל כי העלות הסופית היא $O(m\log ^{*}n)$, כנדרש.

חסם הדוק יותר

למעשה, שימוש בטכניקות שפורטו לעיל יניב סיבוכיות משוערכת של $O(\alpha (n))$ בלבד לכל פעולה, כאשר $\alpha (n)$ היא הפונקציה ההופכית לפונקציה $n=f(x)=A(x,x)$, כאשר $A$ היא פונקציית אקרמן, הידועה בתכונתה כפונקציה שגדלה מהר מאוד. בתור ההופכית לפונקציית אקרמן, $\alpha (n)$ היא בפועל פחות מ-5 לכל ערך מעשי של $n$. לדוגמה, המספר $9876!$, כאשר $!$ הוא אופרטור העצרת, הוא בעל 35,164 ספרות ומתקבל $\alpha (9876!)=5$).

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

פרדמן (Fredman) וסאקס (Saks) הראו בשנת 1989 כי $\Omega (\alpha (n))$ עצמים בהכרח זוכים לגישה על ידי פעולה כלשהי על מבנה הנתונים בממוצע. תוצאה זו מראה כי החסם שנמצא הוא אופטימלי מבחינה אסימפטוטית.

יישומים

איחוד קבוצות זרות יכול להוות מודל של חלוקה של קבוצה, כדי, לדוגמה, לעקוב אחרי רכיבי קשירות בגרף לא מכוון. מודל זה יכול לעזור לנו בקביעה האם זוג צמתים בגרף שייכים לאותו רכיב קשירות, או האם הוספת קשת בין זוג צמתים תגרום ליצירת מעגל. אלגוריתם איחוד-חיפוש נמצא בשימוש נרחב במערכות בעלות ביצועים ברמה גבוהה המממשות איחוד-גרפים (Unification), תהליך החישוב של הגרף הכללי ביותר המכליל את הגרפים שניתנו כקלט. שימוש נוסף לדוגמה למימוש אלגוריתמים בתורת הגרפים, הוא מימוש האלגוריתם של קרוסקל למציאת עץ פורש מינימלי.

מימוש ביטויי שוויון בשפת Fortran עושה שימוש באלגוריתם איחוד-חיפוש.

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

קישורים חיצוניים

• מימוש בשפת C++ כחלק מספריות השירות של Boost עבור שפת C++
• מימוש בשפת ג'אווה, מתוך המהדורה הרביעית של Algorithms מאת Robert Sedgewick and Kevin Wayne
• יישומון עם תצוגה גרפית בשפת ג'אווה, מאת Rory L. P. McGuire
• Wait-free Parallel Algorithms for the Union–Find Problem, מאמר מאת Richard J. Anderson and Heather Woll, המתאר מימוש מקבילי של מבנה הנתונים ללא חסימות
• מימוש בשפת פייתון.
• הסברים עם דוגמאות ומימוש בשפת C#
• Understanding the Inverse Ackermann Function, Raimund Seidel