Задача 1:
Получив на входе корпус языка (огромный набор атрибутированных текстов на каком-нибудь языке) построить частотный словарь. Знаки препинания, скобки, кавычки и числа должны быть удалены. Слова, содержащие в себе не буквенные символы, игнорируются целиком.
Задача 2:
При автоматическом переводе необходимо из нескольких слов выбрать наиболее употребительное. Необходимо построить эффективную реализацию функции, которая для данного множества (Set) слов-ключей, определит то, которому соответствует максимальное значение.
Тест
| input | output |
| aaa for bbb aaa for if %EOF% |
Word frequency statistics:
aaa , 2, 0.250000 Select max frequent token from: for do to while if |
|
To be, or not to be: that is the question: %EOF% |
Word frequency statistics:
And , 5, 0.007321 Select max frequent token from: else for do to while if |
|
#include <iostream> int main() { for( int i = 0; i < 10; i++ ) %EOF% |
Word frequency statistics:
Even , 1, 0.032258 Select max frequent token from: else for do to while if |
Структура программы
Код программы состоит из следующих элементов, объединенных в пакет odessa.uni.imem.maxim:
- Интерфейс FrequencyVocabulary, который описывает заданную функциональность доступа к частотному словарю
- Класс FrequencyVocabularyImpl, имплементирует данный интерфейс
- Класс FrequencyVocabularyTest, который имплементирует тестевое приложение, он содержит метод main и вспомогательные методы ввода данных и вывода результата.
Интерфейс FrequencyVocabulary:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
package odessa.uni.imem.maxim; import java.util.Set; import java.util.Map; import java.util.TreeMap; public interface FrequencyVocabulary { public class Statistic { public int count; public double frequency; public Statistic() { count = 0; frequency = 0; } } public TreeMap<String,Statistic> getMap(); public String selectMaxFreqToken( Set<String> tokens ); } |
Интерфейс подразумевает, что частотный словарь представлен в виде стандартного класса TreeMap. В качестве ключа типа String выступает само слово, а в качестве значения — специальная структура Statistic, содержащая статистику по данному слову, а именно — число вхождений count и частоту frequency.
Интерфейс содержит два метода:
- getMap — возвращает сам частотный словарь как TreeMap объект.
- selectMaxFreqToken — выполняет условие 2-го задания, а именно — выбирает наиболее часто встречаемое слово из заданного набора, передаваемого как аргумент типа Set
Класс FrequencyVocabularyImpl:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 |
package odessa.uni.imem.maxim; import java.util.Set; import java.util.Map; import java.util.TreeMap; import java.util.StringTokenizer; public class FrequencyVocabularyImpl implements FrequencyVocabulary { TreeMap<String, Statistic> map; public FrequencyVocabularyImpl(String text, String delimiters) { map = new TreeMap<String, Statistic>(); int totalCount = 0; // first we parse text to tokens (words) and fill the map where keys are words and values - statistic for given word StringTokenizer st = new StringTokenizer(text, delimiters); while (st.hasMoreTokens()) { String key = st.nextToken(); if ( containsDigits(key) ) { continue; } Statistic value = map.get(key); if (null != value) { value.count++; map.replace(key, value); } else { value = new Statistic(); value.count = 1; map.put( key, value ); } totalCount += value.count; } // now we can calculate and set frequency field for all the entries for (Map.Entry<String, Statistic> entry : map.entrySet()) { if ( entry.getValue().count != 0 ) { entry.getValue().frequency = ((double)entry.getValue().count) / totalCount; } } } public TreeMap<String, Statistic> getMap() { return map; } // select token with max frequency from the given set of tokens public String selectMaxFreqToken( Set<String> tokens ) { String maxFreqToken = null; Statistic maxFreqStat = null; for( String token : tokens ) { Statistic stat = map.get(token); if ( stat != null ) { if ( maxFreqToken == null ) { maxFreqToken = token; maxFreqStat = stat; } else { if ( stat.count > maxFreqStat.count ) { maxFreqToken = token; maxFreqStat = stat; } } } } return maxFreqToken; } public static boolean containsDigits( String token ) { if ( token.indexOf('0') >= 0 || token.indexOf('1') >= 0 || token.indexOf('2') >= 0 || token.indexOf('3') >= 0 || token.indexOf('4') >= 0 || token.indexOf('5') >= 0 || token.indexOf('6') >= 0 || token.indexOf('7') >= 0 || token.indexOf('8') >= 0 || token.indexOf('9') >= 0 ) { return true; } return false; } } |
Класс строит частотный словарь на основе входного текста. Словарь храниться в виде приватного члена типа TreeMap. Для разбора текста на слова используется известный класс StringTokenizer. Конструктор создает класс в 2 прохода. За первый проход заполняется словарь, где для каждого слова заносится статистика с подсчитанным счетчиком вхождений count и пока еще нулевым frequency, однако, вычисляется общий счетчик всех слов totalCount. За второй проход по уже известной статистике каждого слова рассчитывается его frequency как count /totalCount.
Метод containsDigits добавляет проверку для отсеивания лекскм, содержащих цифры согласно требованию 1-й задачи.
Выборка слова с максимальной частотой согласно второй задаче реализована в методе selectMaxFreqToken, где выполняется цикл по всем заданным словам и выбирается слово с максимальным count.
Класс FrequencyVocabularyTest
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 |
package odessa.uni.imem.maxim; import java.util.Set; import java.util.HashSet; import java.util.Map; import java.util.TreeMap; import java.util.NoSuchElementException; import java.io.IOException; import odessa.uni.imem.maxim.FrequencyVocabulary.Statistic; import java.util.Scanner; public class FrequencyVocabularyTest { public static void main(String[] args) { String text = ""; Scanner in = new Scanner(System.in); for(;;) { if ( ! in.hasNextLine() ) break; String inputLine = in.nextLine(); if ( inputLine == null || inputLine.equals("%EOF%") ) break; text = text + inputLine + "\n"; } in.close(); if ( text.isEmpty() ) { System.out.println("*** Empty text ****"); return; } //System.out.println("*** DBG:input text is: <"+text+">"); FrequencyVocabulary fv = new FrequencyVocabularyImpl( text, " ?.,;:-+\n\t{}[]=()<>*&%$#@\"\'`~!" ); TreeMap<String,FrequencyVocabulary.Statistic> statMap = fv.getMap(); System.out.println("Word frequency statistics:\n"); for (Map.Entry<String, Statistic> statEntry : statMap.entrySet()) { System.out.printf("%s\t,\t%d,\t%f\n", statEntry.getKey(), statEntry.getValue().count, statEntry.getValue().frequency ); } System.out.println("--------------------------------------\n"); HashSet<String> tokens = new HashSet<String>(); tokens.add("for"); tokens.add("do"); tokens.add("to"); tokens.add("while"); tokens.add("else"); tokens.add("if"); String caption = "Select max frequent token from: "; for( String s : tokens ) { caption += " " + s; } System.out.println(caption); String s = fv.selectMaxFreqToken(tokens); if ( s == null ) s = "<null>"; System.out.println("=> selected is: " + s ); } } |
В данном классе реализуется приложение, которое тестирует интерфейсные методы частотного словаря. Он состоит из следующих этапов:
- Ввод исходного текста, так как текст может допускать любое количество символов новой строки, и поскольку затруднительно определить признак конца текста как конец файла, в качестве признака конца текста используется спец. лексема %EOF% , которая должна быть после последней строки текста.
- Создание объекта частотного словаря на основе введенного текста, в качестве разделителей используются все известные символы, которые не явл. буквой или цифрой.
- Проход по элементам словаря и печать статистики.
- Тестирование метода, определяющего максимально встречающиеся слова из набора заданных
Примечание: Ввиду того, что затруднительно за один раз ввести с консоли исходный текст для 1-го задания и список слов для 2-го, набор слов для 2-го задания задается в коде непосредственно, а именно do, to, for, while и if.
Код на Ideone: https://ideone.com/jxJ4rU