Виявляється відтоді як я рахував символи вікіпедії пройшло вже більше року. Рахував я їх за допомогою Go, хоча можна було сильно спростити собі життя і рахувати їх за допомогою Python і pywikipediabot. Сьогодні розкажу як, і як можна побачити з назви – рахуватимемо слова.

Я чомусь боявся що щоб порахувати слова пам’яті не вистачить, тому треба якусь базу даних. Або пробувати все в пам’яті, але аби комп’ютеру не стало погано якось обмежити доступну пам’ять. Але мої 4Gb використовувались лише щось трохи більше ніж на 40% для підрахунку всіх слів включно зі сторінками обговорень, категорій, шаблонів, сторінок опису файлів, і т.п. німецької вікіпедії.

В модулі pywikibot.pagegenerators є об’єкти XMLDumpOldPageGenerator і XMLDumpPageGenerator. Вони приймають назву архіву з XML дампом в конструкторі, а після створення по них можна ітеруватися отримуючи об’єкти сторінки. Не ведіться на слово “Old” в назві першого об’єкта, це означає не депрекацію, а те що текст сторінки буде братись з дампа, а в другому випадку з дампа буде братись лише заголовки, а за свіжим текстом зроблять запит, що сповільнить обробку разів в 500. Тобто замість кількох годин ви будете чекати рік.

Я спробував проаналізувати німецьку вікіпедію (код буде пізніше), на це пішло 694 хв (трохи менше ніж 12 годин) і вийшло що в ній на 6,425,028 сторінках використовується 2,381,457,397 слів (приблизно 371 на сторінку), з них різних слів 18,349,393. В кінцевому результаті CSV з частотним словничком виходить на 300MB.

Серед тих що зустрічаються лише раз є слова типу PikettdienstPikettdienst (помилка парсера який видаляв розмітку), слово – це юридичний термін швейцарської німецької і перекладається як “служба за викликом”. І є слова на зразок Werkshöfe – подвір’я фабрик.

Топ 50 слів виглядає так, і складає 28% всіх слів загалом:

До списку потрапили такі вікіпедійно специфічні слова як Kategorie (сторінки без категорій вважаються не комільфо), CEST і CET (центральноєвропейський літній час і центральноєвропейський час, в підписах в обговореннях).

Ну а що без сторінок обговорень? Проблемав тому, що при створенні об’єкту сторінки XMLDumpOldPageGenerator бере з дампа лише текст і заголовок, простір імен залишається не заповненим і за замовчуванням 0 (основний). Є ще поле isredirect так при спробі доступу до нього знову здійснюється запит. Тому, краще перейти на рівень нижче і використати XmlDump з pywikibot.xmlreader, він використовується так само, просто дає об’єкти не Page, а попростіші, які не вміють робити запити до вікіпедії і не мають методу save. Але нам його й не треба, правда?

Ось код який ігнорує перенаправлення і всі сторінки крім статтей:

"""Count word frequencies in wikipedia dump"""
import csv
from collections import Counter
from itertools import islice
import re
import sys

import mwparserfromhell
from pywikibot.xmlreader import XmlDump

def main():
    """Iterate over pages and count words"""
    if len(sys.argv) < 2:
        print('Please give file name of dump')
        return
    filename = sys.argv[1]

    pages = 0
    words = 0
    words_counts = Counter()
    print('Processing dump')

    for page in XmlDump(filename).parse():
        if (page.ns != '0') or page.isredirect:
            continue
        try:
            text = mwparserfromhell.parse(page.text).strip_code()
        except Exception as e:
            print(page.title, e)
            continue

        text = text.replace('\u0301', '') # remove accents
        # Ukrainian: 

        # page_words = re.findall(
        #     r'[абвгґдеєжзиіїйклмнопрстуфхцчшщьюя'
        #     r'АБВГҐДЕЄЖЗИІЇЙКЛМНОПРСТУФХЦЧШЩЬЮЯ’\'-]+',
        #     text
        # )
        
        # Any language:
        page_words = re.findall(r'\b[^\W\d]+\b', text)

        pages += 1
        words += len(page_words)
        words_counts.update(page_words)
        if pages % 123 == 0:
            print('\rPages: %d. Words: %d. Unique: %d. Processing: %s' % (
                pages, words, len(words_counts), (page.title + ' ' * 70)[:70],
            ), end='')

    print('Done. Writing csv')
    with open('common_words.csv', 'w', newline='') as csvfile:
        csvwriter = csv.writer(csvfile)
        for item in words_counts.most_common():
            csvwriter.writerow(item)

if __name__ == '__main__':
    main()

Він працює майже вдвічі швидше, 381 хвилину, бо обробляє лише 2,295,426 сторінок (обсяг німецької вікіпедії цього року). На цих сторінках є 1,074,446,116 слів (в середньому 468 на сторінку), з них різних – 12,002,417. (Виявляється є аж 6 мільйонів всяких слів які вживаються на всіляких службових сторінках німецької вікіпедії, і яких нема в статтях).

Якщо ж взяти українські статті, то на них треба ще менше часу – 131 хвилину (забув уточнити що в мене SSD), їх є 923238 (скоро мільйон!), слів 238263126 (в середньому 258 на сторінку, треба доповнювати ). З них різних – 4,571,418. Отак, в мене тепер є частотний словник української на 4.5 мільйони слів. І німецької на 12 мільйонів.

Хоча не спішіть з висновками що українська мова бідніша, бо мої методи потребують вдосконалення. По перше, так як Morgen (ранок) і morgen (завтра) – різні слова, то я не приводив букви в німецькій до одного регістру. (Правда й в українській забув це зробити).

По друге, в німецькому словнику 350590 разів зустрічається слово “www”, бо я вважав словом будь-яку послідовність літер латинки, а в українській відфільтрував кирилицю. Слово youtube зустрічається 8375 разів, а значить є ризик знайти якесь рідкісне слово на зразок “fCn8zs912OE”.

На WordPress глючить додавання картинок, тому нате вам відео:

А, і ось топ-10 української вікіпедії:

в,4551982
на,3730686
і,3475086
у,3353796
з,3053407
-,2695783
Категорія,2417267
та,2350573
до,1815429
року,1553492

Частота “року” наводить на думку що в українській вікіпедії якийсь перекос на історичні методи викладу.

Для тих кому викликати openssl надоїло. Це дивно, але цього нема в стандартній бібліотеці python, тому:

sudo pip install pycrypto

Тоді:

from Crypto.PublicKey import RSA
from Crypto import Random

private_key = RSA.generate(1024, Random.new().read)
public_key = private_key.publickey()

print(private_key.exportKey().decode('ascii'))
print(public_key.exportKey().decode('ascii'))

Що дасть нам:

-----BEGIN RSA PRIVATE KEY-----
MIICXQIBAAKBgQCFO0e8pxFV5Niq9Kjkn7HpX5xCbsh2oP56t2goNw/qZnddzW1x
... blablabla ...
dB6mvhutUqKRZDaA1o4y1kytKTG42RfEtdm8t1Z/77dS
-----END RSA PRIVATE KEY-----
-----BEGIN PUBLIC KEY-----
MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQCFO0e8pxFV5Niq9Kjkn7HpX5xC
bsh2oP56t2goNw/qZnddzW1xW3rWxYI2/Jxp/hv7EGapg12EcViF/C8Uv2WbCDEM
LIRaMqtHKFNaniscMgZKgaohkjXcLk5dIrVXuuxY7sk07BZqj+Jsv6xgR6GZ0CmG
Q3ZOmGAKksC/YA3gYwIDAQAB
-----END PUBLIC KEY-----

В іншій публікації було показано як це робити допомогою openssl, і як цими ключами підписати токен.

Легко. Давайте напишемо бота який перекладатиме нам всяке з німецької:

Приклад діалогу

Для цього нам треба поговорити з botFather-ом:

А зараз трохи не по темі цієї статті. Ось код який перетворює вікідані на словник, шукаючи всі сутності які мають мітки однією мовою, а потім показучи їх мітки іншою мовою, використовуючи хитрий запит SPARQL:

import json
import requests

def translate(from_lang, to_lang, word):
    '''
        Переклдає мітки елементів вікіданих з мови на мову. Повертає список варіантів перекладу
    '''
    res = sparql('''
        SELECT  ?ukLabel WHERE {
          ?item ?label "%s"@%s.
          ?item rdfs:label ?ukLabel filter(lang(?ukLabel) = "%s")
        } LIMIT 10
    ''' % (word, from_lang, to_lang))
    return list(map(
        lambda e: e['ukLabel']['value'],
        res['results']['bindings']
    ))

def sparql(query):
    ''' Отримує JSON дані запиту SPARQL до вікіданих '''
    res = requests.get(
        'https://query.wikidata.org/sparql',
        params={
            'query': query,
            'format': 'json'
        }
    )
    return json.loads(res.text)

А тепер повертаємось до теми телеграмного бота. Аби його написати треба поставити бібліотеку:

pip install pyTelegramBotAPI

Ось її Github: https://github.com/eternnoir/pyTelegramBotAPI

А далі – елементарно як писати консольну програму:

import telebot

TOKEN = '' # тут вставити те що BotFather сказав

bot = telebot.TeleBot(TOKEN)

@bot.message_handler(content_types=["text"]) # Якщо прийдуть нові повідомлення
def respond_to_message(message):
    translations = translate('de', 'uk', message.text) # Отримати переклади тексту повідомленя
    resp = '\n'.join(translations) if translations else 'На жаль, перекладу слова %s не знайдено' % message.text
    bot.send_message( # відправити назад
        message.chat.id, # в той самий чат з якого прийшло (можна напевне й в інший)
        resp
    )

if __name__ == '__main__':
     bot.polling(none_stop=True) # Запустити бота аби той сидів на лінії і слухав повідомлення.

Поки що все, бо й висипатись іноді треба. Пізніше нагадайте мені не забути написати більше про SPARQL, як поставити собі локальну mediawiki і розширення до неї, як логінити сторонні застосунки через OAuth, і як переписати інтерфейс вікіпедії на Vue.js.

Я не дуже хотів йти на Львів ІТ арену, бо то настільки понтово що задорого. Крім того на вузькоспеціалізованих конференціях на зразок PyCon я мало що розумію, навіть якщо сам доповідаю. Хоча, знаєте, ото щойно передивився одну доповідь – і ніби все зрозумів (а що ще краще, виявляється що викладені там ідеї я зараз використовую в Angular, хоч і забув про них). Крім того, нащо йти на платну конференцію, якщо ти навіть не встигаєш читати всі блоги і дивитись всі безкоштовні відео доповідей з інших конференцій в інтернеті?

Але я пішов, і не пожалів. Познайомився з Естер Дайсон. Вона великий фанат здорового способу життя, і інвестор в наш проект.

Пішов на доповідь про мікросервіси оцього чоловіка. Там дізнався що всі системи які містять багато взаємодіючих компонентів можна описувати наприклад пі-численням. Але так як книжки з пі-числення страшенно дорогі, ось вам безкоштовна про математичну теорію названу “Взаємодія послідовних процесів”, і написана не аби-ким, а Сером Чарлзом Ентоні Річардом Гоаром. Тепер залишилось знайти час прочитати.

А ще поміж іншим дізнався про те що програмне забезпечення це лайно (точніше завжди знав), але існує стрібна куля. Називається LangSec, коли ми вхідні параметри описуємо якоюсь формальною мовою. Чим це відрізняється від Логіки Хоара і наприклад статичної типізації з алгебраїчними типами даних – ще треба подумати.

А ще зустрів хлопців з Quintagroup, вони зразу такі “О, це ти той пітонщик з SoftServe що пише на Zope”. Я такий – той, але вже не пітонщик і не з SoftServe. Зараз вони багато працюють над проектом Prozorro, і шукають нових людей. Тому якщо знаєте Pyramid (чи який там фреймворк у https://github.com/openprocurement), шукаєте роботу – напишіть їм.

Ката – то вправа в східних бойових мистецтвах, набір рухів які треба повторювати поки не засвоїш досконально. Термін застосовується також і для неробочого, неспортивного, самостійного учбового програмування поза якимось проектом.

На моєму домашньому модемі відвалився DSL, то я вчора ввечері не мав чим зайнятись. (Хоча звісно є купа важливіших речей) Зате біля мене була роздруківка книжечки Ніклауса Вірта “Compiler Construction“, то я взявся перекладати його парсер EBNF що ілюструє метод рекурсивного спуску з Oberon на Python. Вийшло ніби незле:

# ebnf.py
import re

class Symbol(object):
    instances = {}
    def __init__(self, name, pattern):
        self.pattern = pattern
        self.regexp = re.compile(pattern)
        self.instances[name] = self

    def match(self, text):
        text = text.lstrip()
        m = self.regexp.match(text)
        if m:
            return m.group(), text[len(m.group()):]

    @classmethod
    def get_next(cls, text):
        if not text.strip():
            return 'empty', '', ''
        for name, sym in cls.instances.items():
            m = sym.match(text)
            if m:
                return name, m[0], m[1]
        raise UnknownSymbolError('Unknown symbol: %r' % text[:50] + (
            '...' if len(text) > 50 else ''
        ))

Symbol('ident', 'w+')
Symbol('literal', '"[^"]*"')
Symbol('eql', '=')
Symbol('lparen', '(')
Symbol('rparen', ')')
Symbol('lbrak', '[')
Symbol('rbrak', ']')
Symbol('lbrace', '{')
Symbol('rbrace', '}')
Symbol('bar', '|')
Symbol('period', '.')

EBNF = '''
syntax = {production}.
production = identifier "=" expression ".".
expression = term {"|" term}.
term = factor {factor}.
factor = identifier | string | "(" expression ")" | "[" expression "]" | "{" expression "}".
'''

def parse_ebnf(text):
    sym, sym_text, remaining = '', '', text
    
    def next():
        nonlocal sym, sym_text, remaining
        sym, sym_text, remaining = Symbol.get_next(remaining)

    next()
    
    def syntax():
        res = ['syntax']
        while sym == 'ident':
            res.append(production())
        return res

    def production():
        name = sym_text
        next()
        if sym == 'eql':
            next()
        else:
            raise ExpectedEqualityError
        exp = expression()
        if sym == 'period':
            next()
        else:
            raise NoPeriodError
        return ['production', name, exp]

    def expression():
        res = ['expression', term()]
        while sym == 'bar':
            next()
            res.append(term())
        return res

    def term():
        res = ['term']
        while sym in ('ident', 'literal', 'lparen', 'lbrak', 'lbrace'):
            res.append(factor())
        if len(res) == 1:
            raise NoFactorError
        return res

    def factor():
        if sym == 'ident':
            res = [sym, sym_text]
            next()
            return res
        elif sym == 'literal':
            res = [sym, sym_text]
            next()
            return res
        elif sym == 'lparen':
            next()
            exp = expression()
            if sym == 'rparen':
                next()
            else:
                raise NoRParenError
            return ['(', exp]
        elif sym == 'lbrak':
            next()
            exp = expression()
            if sym == 'rbrak':
                next()
            else:
                raise NoRBrakError
            return ['[', exp]
        elif sym == 'lbrace':
            next()
            exp = expression()
            if sym == 'rbrace':
                next()
            else:
                raise NoRBraceError
            return ['{', exp]
        else:
            raise RuntimeError(
                "term should be called only when "
                "sym in ('ident', 'literal', 'lparen', 'lbrak', 'lbrace')"
            )

    return syntax()

class UnknownSymbolError(SyntaxError):
    pass

class NoPeriodError(SyntaxError):
    pass

class NoRParenError(SyntaxError):
    pass

class NoRBrakError(SyntaxError):
    pass

class NoRBraceError(SyntaxError):
    pass

class NoFactorError(SyntaxError):
    pass

class ExpectedEqualityError(SyntaxError):
    pass

Трохи TDD, трохи дописування тестів після:

# test.py
from unittest import TestCase, main, skip

from ebnf import Symbol
from ebnf import parse_ebnf, EBNF
from ebnf import print_tree
from ebnf import (
    NoPeriodError, NoRParenError, UnknownSymbolError,
    NoRBrakError, NoRBraceError, NoFactorError
)

class TestSymbol(TestCase):
    def test_paren(self):
        self.assertEqual(
            Symbol.get_next('(asdf)'),
            ('lparen', '(', 'asdf)')
        )
    def test_ident(self):
        self.assertEqual(
            Symbol.get_next('asdf'),
            ('ident', 'asdf', '')
        )
    def test_bar(self):
        self.assertEqual(
            Symbol.get_next('|asdf'),
            ('bar', '|', 'asdf')
        )

class TestEBNF(TestCase):
    def test_self(self):
        tree = parse_ebnf(EBNF)
        self.assertEqual(
            parse_ebnf(EBNF),
            ['syntax',
             ['production',
              'syntax',
              ['expression',
               ['term', ['{', ['expression', ['term', ['ident', 'production']]]]]]],
             ['production',
              'production',
              ['expression',
               ['term',
                ['ident', 'identifier'],
                ['literal', '"="'],
                ['ident', 'expression'],
                ['literal', '"."']]]],
             ['production',
              'expression',
              ['expression',
               ['term',
                ['ident', 'term'],
                ['{', ['expression', ['term', ['literal', '"|"'], ['ident', 'term']]]]]]],
             ['production',
              'term',
              ['expression',
               ['term',
                ['ident', 'factor'],
                ['{', ['expression', ['term', ['ident', 'factor']]]]]]],
             ['production',
              'factor',
              ['expression',
               ['term', ['ident', 'identifier']],
               ['term', ['ident', 'string']],
               ['term', ['literal', '"("'], ['ident', 'expression'], ['literal', '")"']],
               ['term', ['literal', '"["'], ['ident', 'expression'], ['literal', '"]"']],
               ['term', ['literal', '"{"'], ['ident', 'expression'], ['literal', '"}"']]]]]
        )

    def test_without_period(self):
        with self.assertRaises(NoPeriodError):
            parse_ebnf('symbol = "asdf"')

    def test_without_rparen(self):
        with self.assertRaises(NoRParenError):
            parse_ebnf('symbol = ("asdf"')

    def test_without_rbrak(self):
        with self.assertRaises(NoRBrakError):
            parse_ebnf('symbol = ["asdf"')

    def test_without_rbrace(self):
        with self.assertRaises(NoRBraceError):
            parse_ebnf('symbol = {literal')

    def test_unknown_symbol(self):
        with self.assertRaises(UnknownSymbolError):
            parse_ebnf('!symbol = "asdf"')

    def test_no_factor(self):
        with self.assertRaises(NoFactorError):
            parse_ebnf('sym = ||')

    def test_for_binary(self):
        self.assertEqual(
            parse_ebnf('''
                digit = "0"|"1".
                number = digit {digit}.
            '''),
            ['syntax',
             ['production',
              'digit',
              ['expression', ['term', ['literal', '"0"']], ['term', ['literal', '"1"']]]],
             ['production',
              'number',
              ['expression',
               ['term',
                ['ident', 'digit'],
                ['{', ['expression', ['term', ['ident', 'digit']]]]]]]]
        )


if __name__ == '__main__':
    main()

І я зрозумів дві речі: що найбільше на світі (якщо не враховувати сну) люблю писати код, і що таке множина . Якщо коротко, то це множина символів з яких може починатись рядок що виводиться з нетерміналу k. Наприклад:

digit = "0" | "1"
number = digit {digit}

first(number) = {"0", "1"}

І ми знаємо що парсер може прочитати не будь-яку граматику, а лише ту, в якої для кожного виразу на зразок

definition = exp1 | exp2

Виконується умова:

Таким чином отака граматика багатозначна:

sum = number | sum ("+" | "-") sum

Бо вираз 1 – 10 + 11 можна розпарсити як (1 – 10) + 11 або як 1 – (10 + 11). А все тому, що .

Її можна переписати так щоб в правилі для суми не було двох варіантів що починаються з однакових символів.

sum = number {("+" | "-") number}

Так вся сума розгортатиметься зразу і не буде проблем з тим яку операцію виконувати швидше.

Тепер би ще змусити його автоматично генерувати код парсера за EBNF і вийде власний YACC. :)