Як зібрати биграммы для корпусу будь-якого розміру на домашньому комп'ютері

У сучасної комп'ютерної лінгвістики биграммы, або в загальному випадку n-грами, є важливим статистичним інструментом. У статті ми розповімо з якими труднощами можна зіткнутися при розрахунку биграмм на великому корпусі текстів і наведемо алгоритм, який можна використовувати на будь-якому домашньому комп'ютері.

Біграм — це два слова, які в тексті або, в нашому випадку в корпусі текстів, є сусідніми. Наприклад у реченні:

Це було жарким літом.
1 2 3 4 5 (пробіл після "влітку" не є помилкою або помилкою)

будуть такі биграммы:

  • Це було
  • було спекотним
  • жарким літом
  • влітку .
Строго кажучи биграммы складаються не зі слів, а з токенів. Токеном, тобто неподільною одиницею в рамках нашої задачі, буде або слово, або пунктуаційний знак. Токенизация — непроста тема, тому будемо вважати, що наш корпус вже токенизирован і розбитий на речення, а щоб перетворити пропозицію в список токенів, достатньо розбити його по прогалині.

Нашої завданням буде отримати такий список:

  • Це було 190360
  • було спекотним 1017
  • жарким літом 2621
  • влітку . 42146
де число показує скільки разів зустрічається біграм у всьому корпусі.

Іноді в тексті ми дозволимо собі використовувати термін двусочетание як синонім до слова біграм.

У даній статті ми навмисно опустили всі деталі реалізації, т. к. підхід цікавий сам по собі і реалізувати його нескладно на вашому улюбленому мовою програмування. До того ж реалізація містить в собі достатню кількість цікавих деталей, щоб поговорити про неї в окремій статті. Мінімальна кількість пояснювальних ремарок буде даватися на мові Java.

Наївний підхід
  • бігти по корпусу
  • з кожного речення виділяти биграммы
  • вважати їх за допомогою структури даних мультимножество (на Java це Multiset<String> або ConcurrentHashMultiset<String> в багатопотоковому варіанті)
На відносно невеликому і чистому корпусі може спрацювати, але в загальному випадку при наївному підході пам'ять у вас закінчиться раніше, ніж ви встигнете порахувати весь масив текстів.

Додаємо проміжні відсікання
Наївний підхід дуже просто перетворити в робочий, якщо трохи його модифікувати:

  • бігти по корпусу
  • з кожного речення виділяти биграммы
  • вважати їх за допомогою мультимножества
  • як тільки бачимо, що закінчується пам'ять — чистимо лічильник, видаляючи биграммы, які зустрілися до цього моменту менше ніж граничне число разів
Ця модифікація дає цілком робочий алгоритм, але відсікання приносять одну неприємність: разом з непотрібним шумом, яким є нерегулярні помилки і помилки, ми видалимо безліч корисної інформації про рідкісних словах. Наприклад, якщо лексема (набір словоформ) зустрічається в корпусі 1000 раз, то кожна її окрема словоформа може зустрічатися, скажімо, менше 200 разів на корпус, а що вже говорити про двусочетаниях.

Наше завдання полягає в тому, щоб порахувати биграммы максимально чесно, не використовуючи проміжних відсікань.

Використовуємо диск в якості тимчасової пам'яті
Оперативна пам'ять зараз коштує відносно недорого, але все ж варто. До того ж багато варіантів ноутбуків більше 16 гігабайт ви не встановите при всьому бажанні — обмеження платформи. З дисковим ж простором ніяких проблем немає — воно коштує істотно дешевше і при бажанні ви завжди можете використовувати зовнішній накопичувач.

При згадці смислових тегів #жесткий_диск і #алгоритм у пам'яті спливають алгоритми сортування злиттям (merge sort) і об'єднання впорядкованих списків, які багато писали в школі ще на мові Pascal. Ідеї, закладені в основі цих алгоритмів, як ніяк добре підходять для рішення нашої задачі.

Принципова схема рішення задачі
Перш ніж перейти до деталей, уявімо принципову схему вирішення поставленого завдання:

  1. Розбити корпус на приблизно однакові блоки, скажімо по 1 гігабайту.
  2. Порахувати биграммы окремо для кожного блоку, відсортувати їх у лексикографічному порядку і записати на диск.
  3. Використовуючи алгоритм злиття впорядкованих списків, об'єднати окремі файли з двусочетаниями в один, підсумовуючи кількість входжень для співпадаючих биграмм.
Розмір кожного блоку можна вибирати за смаком (читай: за кількістю встановленої оперативної пам'яті), але в більшості задач розмір у гігабайт виявляється більш ніж зручним. Також можна працювати з монолітним корпусом, роблячи в програмі відсічення за розміром обробленого тексту, скидаючи результат на диск і очищаючи структури даних.

Подивившись на алгоритм з висоти пташиного польоту можна перейти до деталей.

Вважаємо биграммы для кожного блоку
Щоб побудувати оптимальну архітектуру для лічильника двусочетаний, врахуємо дві важливі вимоги:

  1. Хочемо вважати в кілька потоків.
  2. На виході потрібно отримати відсортований в лексикографічному порядку список биграмм.
Так виходить, що ці дві задачі можна ефективно вирішувати разом. Пропонується замість використання однорівневою карти (мультимножество це по суті карта ключ-лічильник)

ConcurrentHashMultiset<String>

для підрахунку биграмм використовувати карту карт:

ConcurrentMap<String, ConcurrentHashMultiset<String>>

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

Ще одна важлива перевага, яку дає використання дворівневої карти: можна дуже швидко робити додаткову фільтрацію за словами биграммы. Наприклад перевірити їх входження в словник або навіть виконати нормалізацію (швидкою їздою -> швидка їзда). Проводити ці операції до того, як ви згрупували однакові двусочетания дуже накладно, оскільки одна і та ж операція буде проводиться безліч разів.

Об'єднуємо результати по всім блокам
Отже, на виході попереднього алгоритму ми маємо безліч файлів із записами виду:

bigram1 count1
bigram2 count2
...
bigramN countN

де ключі відсортовані в лексикографічному порядку. Наше завдання об'єднати ці файли в один, підсумовуючи кількість входжень для відповідних ключів. Завдання підсумовування двох файлів будемо вважати тривіальною і залишимо без додаткових пояснень.

Загальну задачу об'єднання всіх файлів можна вирішити з використанням файлу-акумулятора, послідовно додаючи до нього файли окремих блоків:

(((((( N1 + N2) + N3) + N4) + N5) + N6) + N7)...

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

Для реалізації відмінно підходить кістяк сортування злиттям, використовує рекурсію. Схематично для 15 файлів це буде виглядати так (у функції merge перший індекс включений, другий — виключено):

|_ merge(0, 15) = merge(0, 7) + merge(7, 15)
|_ merge(0, 7) = merge(0, 3) + merge(3, 7)
|_ merge(0, 3) = 0 + merge(1, 3)
|_ merge(1, 3) = 1 + 2
|_ merge(3, 7) = merge(3, 5) + merge(5, 7)
|_ merge(3, 5) = 3 + 4
|_ merge(5, 7) = 5 + 6
|_ merge(7, 15) = merge(7, 11) + merge(11, 15)
|_ merge(7, 11) = merge(7, 9) + merge(9, 11)
|_ merge(7, 9) = 7 + 8
|_ merge(9, 11) = 9 + 10
|_ merge(11, 15) = merge(11, 13) + merge(13, 15)
|_ merge(11, 13) = 11 + 12
|_ merge(13, 15) = 13 + 14

В результаті алгоритм зробить ті ж 14 злиттів, але відпрацює при цьому набагато ефективніше варіанту з акумулятором. Теоретичні вимоги по пам'яті алгоритму злиття O(1), а на практиці пам'ять виділяється тільки під буфери читання і запису.

висновок
Використовуючи наведений підхід можна збирати по корпусу не тільки биграммы, але і n-грами для будь-якого n. Хоча там, можливо, доведеться використовувати блоки меншого розміру і частіше скидати проміжні результати на диск.

Як ми і говорили на початку, деталі реалізації заслуговують окремої розмови і про них ми розповімо в наступній статті.
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.