Приводится C#-программа, исправляющая ошибки в указанном слове. Программа основана на подходе, приведенном в [1]. Часть кода взята из [2].
Программа работает и с русскими, и английскими словами. Ее интерфейс приведен на рис. 1.
Рис. 1. Интерфейс программы "Правка слова"
Программа использует файлы частотныйСловарь.txt и freqList.txt, сформированные по русскому и английскому частотным словарям. Они приведены соответственно в [3] и [4].
При необходимости здесь можно загрузить архив с файлами частотных словарей.
Если установлен флажок Использовать базу, то частотный словарь загружается из таблицы freq базы CrPr. Таблица имеет два поля: word char(30) и freq типа numeric(8, 1).
Файлы частотныйСловарь.txt и freqList.txt формируются соответственно по файлам частотныйСловарьЭлектроннаяВерсия.txt и freqListWiktionary.txt, взятым из [3] и [4].
Создание файлов частотныйСловарь.txt и freqList.txt обеспечивает процедура buttonMakeFile_Click, выполняемая после нажатия на кнопку Файл (рис. 1).
Начальные части файлов частотныйСловарьЭлектроннаяВерсия.txt и freqListWiktionary.txt приведены в табл. 1 и табл. 2.
| Лемма | Лемма | Часть речи | Частота (ipm) | Худ.лит.1950-60-е | 1970-80-е | 1990-2000-е | Публ. 1950-60-е | 1970-80-е | 1990-2000-е | |
| 1 | и | и | conj | 35801.8 | 37546.0 | 39187.7 | 36514.7 | 36703.6 | 38352.1 | 35539.5 |
| 2 | в | в | pr | 31374.2 | 23943.5 | 25005.7 | 26185.7 | 35295.3 | 33264.3 | 36372.5 |
| 3 | не | не | part | 18028.0 | 21154.3 | 22921.5 | 22349.1 | 16127.4 | 18796.9 | 16853.2 |
| Rank | Word | Count (per billion) |
| 1 | the | 56271872 |
| 2 | of | 33950064 |
| 3 | and | 29944184 |
Начальные части файлов частотныйСловарь.txt и freqList.txt приведены в табл. 3 и табл. 4.
Таблица 3. Начальная часть файла частотныйСловарь.txt| и | 35801.8 |
| в | 31374.2 |
| не | 18028.0 |
| the | 56271872 |
| of | 33950064 |
| and | 29944184 |
В первом столбце каждого файла приведено слово, а во втором – его частота.
Предварительно по файлу частотныйСловарь.txt (или freqList.txt) процедурой Spelling формируется частотный словарь dictionary, каждый элемент которого – это пара "ключ и значение".
В качестве ключа выступает слово, а значения – его частота.
Пусть задано слово "карова". Чтобы получить "корова", реализуется следующая последовательность действий:
Программа реализована на C# как Windows Forms Application:
using System;
using System.Collections.Generic; // Dictionary, List
using System.Linq; // ToList, OrderByDescending
using System.Text; // Encoding
using System.Windows.Forms;
using System.IO; // StreamReader
using System.Data.SqlClient; // Если checkBoxWithBase.Checked
namespace WindowsFormsApplicationSpellCorrector
{
public partial class FormSpellCorrector : Form
{
Spelling spelling;
public FormSpellCorrector()
{
InitializeComponent();
spelling = new Spelling(radioButtonRus.Checked, checkBoxWithBase.Checked);
spelling.twoLevelsChecked = checkBoxTwoLevels.Checked;
spelling.writeListsChecked = checkBoxWriteLists.Checked;
}
private void buttonMakeFile_Click(object sender, EventArgs e)
{
StreamReader sR;
StreamWriter sW;
int k = 0;
string s;
if (radioButtonRus.Checked)
{
sR = new StreamReader("частотныйСловарьЭлектроннаяВерсия.txt", true);
sW = new StreamWriter("частотныйСловарь.txt", false, Encoding.Unicode);
string[] arrS = new string[11];
for (k = 0; k < 7; k++) sR.ReadLine(); // Пропускаем 7 строк
k = 0;
while (!sR.EndOfStream)
{
s = sR.ReadLine();
arrS = s.Split('\t');
sW.WriteLine(arrS[1] + '\t' + arrS[4]); // Слово и его частота
k++;
}
}
else
{
sR = new StreamReader("freqListWiktionary.txt");
sW = new StreamWriter("freqList.txt");
string[] arrS = new string[3];
sR.ReadLine(); sR.ReadLine(); // Пропускаем 2 строки
k = 0;
while (!sR.EndOfStream)
{
s = sR.ReadLine();
arrS = s.Split('\t');
if (arrS[0].Length == 4 && arrS[0] == "Rank") continue;
sW.WriteLine(arrS[1] + '\t' + arrS[2]); // Слово и его частота
k++;
}
}
sR.Close();
sW.Close();
spelling = new Spelling(radioButtonRus.Checked, checkBoxWithBase.Checked);
spelling.twoLevelsChecked = checkBoxTwoLevels.Checked;
spelling.writeListsChecked = checkBoxWriteLists.Checked;
MessageBox.Show("Готово: " + k);
}
private void buttonDoCorr_Click(object sender, EventArgs e)
{
string word = textBoxWordToCorrect.Text.Trim();
textBoxWordAfterCorr.Text = string.IsNullOrEmpty(word) ? "Пусто" : spelling.Correct(word.ToLower());
}
private void buttonClose_Click(object sender, EventArgs e)
{
Close();
}
private void radioButtonRus_CheckedChanged(object sender, EventArgs e)
{
if (!radioButtonRus.Checked) checkBoxWithBase.Checked = false;
spelling = new Spelling(radioButtonRus.Checked, checkBoxWithBase.Checked);
spelling.twoLevelsChecked = checkBoxTwoLevels.Checked;
spelling.writeListsChecked = checkBoxWriteLists.Checked;
}
private void checkBoxTwoLevels_CheckedChanged(object sender, EventArgs e)
{
spelling.twoLevelsChecked = checkBoxTwoLevels.Checked;
}
private void checkBoxWriteLists_CheckedChanged(object sender, EventArgs e)
{
spelling.writeListsChecked = checkBoxWriteLists.Checked;
}
private void buttonClear_Click(object sender, EventArgs e)
{
textBoxWordAfterCorr.Text = "";
}
private void checkBoxWithBase_CheckedChanged(object sender, EventArgs e)
{
buttonMakeFile.Enabled = !checkBoxWithBase.Checked;
radioButtonRus.Checked = true;
spelling = new Spelling(radioButtonRus.Checked, checkBoxWithBase.Checked);
spelling.twoLevelsChecked = checkBoxTwoLevels.Checked;
spelling.writeListsChecked = checkBoxWriteLists.Checked;
}
}
public class Spelling
{
private Dictionary<string, int> dictionary = new Dictionary<string, int>();
private bool Rus;
public bool writeListsChecked, twoLevelsChecked;
// Если используется БД, то словарь dictionary формируется по файлу freq базы данных CrPr,
// содержащей морфологический словарь русского языка
// В противном случае формируем dictionary по файлу частотныйСловарь.txt или freqList.txt
// Для каждого слова в dictionary указана частота его употребления
// Первые три строки файла freqList.txt (разделитель - знак табуляции):
// the 56271872
// of 33950064
// and 29944184
public Spelling(bool RusChecked, bool BaseChecked)
{
string key;
int freq; // Частота слова
Rus = RusChecked;
if (BaseChecked)
{
SqlConnection con = new SqlConnection("Data Source=HP-PC\\SQLEXPRESS;Initial Catalog=CrPr;Integrated Security=SSPI;");
SqlCommand command = new SqlCommand();
command.Connection = con;
command.CommandText = "select word, freq from freq";
command.Connection.Open();
SqlDataReader reader = command.ExecuteReader();
while (reader.Read())
{
key = reader.GetString(0).TrimEnd().ToLower();
freq = Convert.ToInt32(reader.GetDecimal(1));
if (!dictionary.ContainsKey(key)) dictionary.Add(key, freq); // В файле могут быть повторяющиеся слова
}
command.Connection.Close();
con.Close();
}
else
{
string fileContent;
fileContent = File.ReadAllText((Rus ? "частотныйСловарь.txt" : "freqList.txt"));
List<string> wordList = fileContent.Split(new string[] { "\n" }, StringSplitOptions.RemoveEmptyEntries).ToList();
string[] arrS = new string[2];
foreach (string word in wordList)
{
arrS = word.Split('\t'); // В случае freqList.txt в строке 1: arrS[0] = "the"; arrS[1] = "56271872"
key = arrS[0].Trim().ToLower();
arrS = arrS[1].Split('.');
freq = Convert.ToInt32(arrS[0]);
if (!dictionary.ContainsKey(key)) dictionary.Add(key, freq); // В файле могут быть повторяющиеся слова
}
}
}
public string Correct(string word)
{
if (dictionary.ContainsKey(word)) return word; // Слово имеется в словаре
Dictionary<string, int> candidates = new Dictionary<string, int>();
List<string> wordVariations = makeVariations(word); // Формируем список модификаций слова без повтров
foreach (string item in wordVariations)
if (dictionary.ContainsKey(item)) candidates.Add(item, dictionary[item]); // Слово и его частота
if (writeListsChecked)
{
List<string> can = new List<string>(); // Для печати
foreach (KeyValuePair<string, int> k in candidates) can.Add(k.Key + " " + k.Value);
writeList(can, "can");
}
// Сортировка списка candidates по убыванию частоты слова
if (candidates.Count > 0) return candidates.OrderByDescending(x => x.Value).First().Key;
if (twoLevelsChecked)
{
// Формируем список модификаций, добавляя в него модификации каждого слова списка wordVariations
foreach (string item in wordVariations)
foreach (string item2 in makeVariations(item))
if (!candidates.ContainsKey(item2) && dictionary.ContainsKey(item2)) candidates.Add(item2, dictionary[item2]);
if (writeListsChecked)
{
List<string> can = new List<string>(); // Для печати
foreach (KeyValuePair<string, int> k in candidates) can.Add(k.Key + " " + k.Value);
writeList(can, "can");
}
// Сортировка списка candidates по убыванию частоты слова
return (candidates.Count > 0) ? candidates.OrderByDescending(x => x.Value).First().Key : word;
}
else
return word;
}
private List<string> makeVariations(string word)
{
var splits = new List<Tuple<string, string>>(); // Список кортежей
// Списки с модификациями word
// m - число букв в слове
// n - число букв в алфавите
var deletes = new List<string>(); // Каждая модификация - это word без одного символа
var transposes = new List<string>(); // Каждая модификация - это word с переставленными соседними символами
var replaces = new List<string>(); // Каждая модификация - это word с замененным символом; число замен: m * n
var inserts = new List<string>(); // Каждая модификация - это word со вставленным символом; число вставок: m * n
// Разбиваем word на 2 куска и заносим их в список splits
for (int i = 0; i < word.Length; i++)
{
var tuple = new Tuple<string, string>(word.Substring(0, i), word.Substring(i)); // Кортеж двух кусков word
splits.Add(tuple);
}
// Формируем списки с модификациями исходного слова
for (int i = 0; i < splits.Count; i++)
{
string a = splits[i].Item1;
string b = splits[i].Item2;
deletes.Add(a + b.Substring(1));
if (b.Length > 1) transposes.Add(a + b[1] + b[0] + b.Substring(2));
if (Rus)
for (char c = 'а'; c <= 'я'; c++)
{
replaces.Add(a + c + b.Substring(1));
inserts.Add(a + c + b);
}
else
for (char c = 'a'; c <= 'z'; c++)
{
replaces.Add(a + c + b.Substring(1));
inserts.Add(a + c + b);
}
}
if (writeListsChecked)
{
writeList(deletes, "del");
writeList(transposes, "tra");
writeList(replaces, "rep");
writeList(inserts, "ins");
writeList(deletes.Union(transposes).Union(replaces).Union(inserts).Distinct().ToList(), "all");
}
// Возвращаем список модификаций слова без повторов (употребляем Distinct)
return deletes.Union(transposes).Union(replaces).Union(inserts).Distinct().ToList();
}
private void writeList(List<string> list, string file)
{
StreamWriter sW = new StreamWriter(file + ".txt", false, Encoding.Unicode);
sW.WriteLine("" + list.Count);
foreach (string s in list) sW.WriteLine('"' + s + '"');
sW.Close();
}
}
}
Приведенная программа исправления слова занимается перебором его модификаций.
Время поиска ответа стремительно растет с ростом длины исследуемого слова. По этой причине для практических целей такой подход непригоден.
(Скорость не будет сильно зависеть от длины слова, если отказаться от второго уровня правки.)
Второй недостаток в том, что из множества кандидатов выбирается слово с наибольшей частотой.
Так, если задано слово "ограненный" и имелось в виду слово "граненый", то при двухуровневой правке список кандидатов будет следующим:
граненый 3
огненный 15
ограниченный 26
И вместо "граненый" будет дан ответ "ограниченный", поскольку его частота наибольшая среди кандидатов.
Область действия программы ограничивает частотный словарь, в котором не представлены некоторые части речи, например деепричастия.
Кроме того, если опираться на частотный словарь, то нужно учитывать, что для каждого вида текстов (художественных, технических, политических и пр.) нужно иметь "свои" словари.
Нелишне сказать, что более востребован поиск и исправление ошибок в предложении, для чего приведенная программа неприспособлена.