רשימת המילים בעברית בפחות מ-50 שורות קוד

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

שניה לפני שהתייאשתי נזכרתי שאני מתכנת והחלטתי לנצל את ההזדמנות כדי לייצר רשימה כזאת בעצמי, ואתם הרווחתם עוד פוסט :)

איך נייצר את הרשימה?

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

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

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

החומרים הדרושים

כדי לקרוא קוד HTML נשתמש בספרייה BeautifulSoup, ובספריית re הסטנדרטית של python. המחלקה Counter מהמודול collections תשמש לשמירת מיפוי בין כל מילה למספר ההופעות שלה, והספרייה progressbar2 תשמש ליצירת מד התקדמות.

from bs4 import BeautifulSoup
from collections import Counter
from progressbar import ProgressBar
import re, os

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

שלב ראשון – יצירת רשימה של שמות הקבצים

נתחיל בחילוץ (unzipping) הקובץ שהורדנו, המכיל את כל הערכים בויקיפדיה, ע"י שימוש בתוכנה 7Zip. התוצאה היא עץ תיקיות ענקי המחולק לתיקיות לפי האות הראשונה של שם הערך, לאחר מכן האות השנייה וכו'. נרצה לעבור על כל הקבצים בעץ, ולשמור את הנתיבים שלהם ברשימה אחת ארוכה.

נעשה זאת ע"י שימוש בפונקציה walk של מודול os, המקבל תיקייה, ומחזירה איטרטור (iterator) על כל הקבצים והתיקיות בה בצורה רקורסיבית:

all_files = []
for root, folders, filenames in os.walk(u'wikipedia-he-html'):
  for filename in filenames:
    all_files.append(os.path.join(root, filename))

שימו לב שאנו מעבירים לפונקציה את שם התיקייה בתור מחרוזת unicode (מתחילה באות u). דבר זה נדרש כדי שהפונקציה תתמוך בנתיבים המכילים עברית.

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

נסו להדפיס את אורך הרשימה all_files כדי לוודא שהיא אכן ארוכה מאוד.

שלב שני – קריאת תוכן הקבצים

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

with ProgressBar(max_value = len(all_files)) as progress:
  for i, file_path in enumerate(all_files):
    progress.update(i)
    html = open(file_path, "rb").read().decode('utf8')

שימו לב שקריאת הקובץ מורכבת משלושה שלבים:

  1. פתיחת הקובץ לקריאה באמצעות הפונקציה open. בחלק ממערכות ההפעלה (בעיקר Windows) חשוב להעביר את הפרמטר "rb" (שמשמעותו read binary) כדי שהקובץ ייקרא בדיוק כמו שהוא.
  2. קריאת תוכן הקובץ לתוך מחרוזת ע"י הפונקציה read.
  3. פתיחת הקידוד של הקובץ, כלומר המרת תוכנו מפורמט בינארי בקידוד UTF-8 למחרוזת מסוג unicode, ע"י הפונקציה decode.

אם שאלתם את עצמכם איך אנחנו יודעים שקידוד הקובץ הוא UTF-8, התשובות הן: (א) זהו הקידוד הנפוץ ביותר לדפי HTML; (ב) כמעט כל עורך טקסט מתקדם יזהה זאת עבורכם כשתפתחו באמצעותו את אחד הקבצים; (ג) זה כתוב בתוך הקבצים: charset=UTF-8.

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

all_files = all_files[:1000]

כעת נסו להריץ את הקוד, סביר להניח שקיבלתם את השגיאה הבאה:

UnicodeDecodeError: 'utf8' codec can't decode byte 0x89 in position 0: invalid start byte

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

try:
  html = open(file_path, "rb").read().decode('utf8')
except UnicodeDecodeError:
  continue

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

שלב שלישי – מציאת כל הטקסט בעמוד

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

הדרך הפשוטה ביותר היא שימוש בספרייה BeautifulSoup הנועדה לפענוח קוד HTML:

soup = BeautifulSoup(html, 'html.parser')
for p in soup.find_all('p'):
  # do something with p

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

דרך חלופית ומהירה הרבה יותר היא מציאת כל התגיות <p> בקובץ ע"י שימוש בביטויים רגולרים (regular expressions), ופענוח התוכן שלהן בלבד:

PARAGRAPHS_PATTERN = re.compile(r"<p>(.*?)</p>")

for p_html in PARAGRAPHS_PATTERN.findall(html):
  p = BeautifulSoup(p_html, 'html.parser')

נתעכב על הביטוי הרגולרי: הוא מתחיל בתגית הפותחת <p> ומסתיים בתגית הסוגרת </p>. תוכן התגית מותאם (matched) ע"י הביטוי הנפוץ נקודה-כוכבית, והוא בתוך סוגריים מכיוון שרק בו אנו מעוניינים, ללא תגיות הפסקה. אך מה פשר סימן השאלה?

נניח שיש לנו שתי פסקאות בעמוד:

<p>hello from icode.co.il</p>
<p>don't forget to subscribe</p>

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

<p>hello from icode</p>
<p>don't forget to subscribe</p>

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

<p>hello from icode</p>
<p>don't forget to subscribe</p>

חשוב לציין שהשימוש בביטוי רגולרי לפענוח HTML לא תמיד יעבוד, מכמה סיבות:

  1. פעמים רבות התגית p תכיל תכונות (attributes) שונות, למשל <p class="blue">, ולכן לא תיתפס ע"י הביטוי הרגולרי. בויקיפדיה תגיות הפסקה לא מכילות תכונות.
  2. במידה ותגית p נמצאת בתוך תגית p אחרת, הביטוי הרגולרי יחזיר תוצאה שגויה. אמנם הדבר לא חוקי בקוד HTML, אך אתרים רבים עדיין מבצעים את הטעות הזאת, והדפדפנים סלחנים כלפיה. למזלנו בויקיפדיה קוד ה-HTML הוא תקני (ואף מיוצר אוטומטית), ולכן הבעיה הזאת לא קיימת.

בשלב זה המשתנה p מכיל אובייקט מטיפוס Tag (של BeautifulSoup), המכיל ייצוג כלשהו של תוכן הפסקה. אך זה עדיין לא מספיק, מכיוון שהייצוג הזה עלול להכיל בעצמו קוד HTML:

<p>hello from <a href="/">icode</a><p>

למזלנו, BeautifulSoup מספקת פונקציה פשוטה להמרת קוד HTML לטקסט:

p_text = p.get_text() # => "hello from icode"

שלב רביעי ואחרון – חלוקה למילים וספירתן

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

words = p_text.split()

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

CHARS_PATTERN = re.compile(ur"""[^אבגדהוזחטיכלמנסעפצקרשתןףץםך'\- "]""")
p_text = CHARS_PATTERN.sub('', p_text)

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

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

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

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

  • קובץ הקוד שלנו צריך להיות שמור בקידוד UTF-8. רוב עורכי הטקסט תומכים בשמירה בקידוד זה.
  • מחרוזות המכילות עברית חייבות להתחיל בתו u (מסמל unicode) לפני המחרוזת.
  • יש להוסיף בתחילת הקובץ את ההערה הבאה:
# -*- coding: utf-8 -*-

כעט נשתמש במבנה הנתונים Counter כדי לספור כמה מופעים יש מכל מילה:

freq = Counter()

for word in words:
  word = word.strip('="')
  if len(word) > 1:
    freq[word] += 1

בקטע קוד זה אנו מבצעים 3 פעולות עבור כל מילה:

  1. משתמשים בפונקציה strip כדי להסיר מקפים וגרשיים המופיעים בתחילתה או בסופה (למשל המילה "ב-" תהפוך למילה "ב").
  2. מוודאים שהמילה היא באורך שני תווים לפחות, כדי לדלג על אותיות קישור המופרדות במקף.
  3. מגדילים באחד את מספר ההופעות ב-Counter שלנו (במידה ואין עדיין הופעות, Counter דואג לאתחל אוטומטית את מספר ההופעות ל-0).

סיימנו! בסיום הריצה המשתנה freq הוא Counter (סוג של מילון) שמפתחותיו הן כל המילים, וערכיו הם מספר ההופעות של כל מילה בכל הטקסט. כל שנשאר הוא לשמור לקובץ בפורמט לבחירתנו, למשל:

open('words.txt', "wb").write(
  u"\n".join("%s, %s" % x for x in freq.most_common()).encode('utf8'))

חשוב לזכור לקודד כ-UTF-8 (או קידוד אחר התומך בעברית) טרם השמירה.

קובץ המילים אמור להיראות כך:

של, 523462
את, 362830
על, 280208
הוא, 155791
לא, 122371
...
פילי, 44
הלשכות, 44
שליחו, 43
בבואה, 43
...

העשרה: שיפור מהירות הריצה

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

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

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

נסו לעבור על הקוד המלא ולמצוא אותן.

מה הלאה?

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

  1. זיהוי והסרת אותיות קישור מהמילים. למשל המילה "במכונית" תיספר כמו המילה "מכונית"
  2. הסרת מילים שתדירותן נמוכה מדי
  3. שימוש במקור טקסט אחר
  4. השוואה בין מקורות טקסט שונים ליצירת רשימת מילים שאינה מוטה למקור מסויים
  5. חיפוש ביטויים נפוצים במקום מילים נפוצות
  6. תמיכה בשפות נוספות
  7. שימוש ב-dump עדכני יותר של ויקיפדיה (קיים בפורמטים שאינם HTML)

הקוד המלא

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