Список работ

Исправление ошибок в слове

Содержание

Введение

Приводится C#-программа, исправляющая ошибки в указанном слове. Программа основана на подходе, приведенном в [1]. Часть кода взята из [2].

Программа работает и с русскими, и английскими словами. Ее интерфейс приведен на рис. 1.

Интерфейс программы

Рис. 1. Интерфейс программы "Правка слова"

Программа использует файлы частотныйСловарь.txt и freqList.txt, сформированные по русскому и английскому частотным словарям. Они приведены соответственно в [3] и [4].
При необходимости здесь можно загрузить архив с файлами частотных словарей.

Формирование файлов по частотным словарям

Файлы частотныйСловарь.txt и freqList.txt формируются соответственно по файлам частотныйСловарьЭлектроннаяВерсия.txt и freqListWiktionary.txt, взятым из [3] и [4].
Создание файлов частотныйСловарь.txt и freqList.txt обеспечивает процедура buttonMakeFile_Click, выполняемая после нажатия на кнопку Файл (рис. 1).
Начальные части файлов частотныйСловарьЭлектроннаяВерсия.txt и freqListWiktionary.txt приведены в табл. 1 и табл. 2.

Таблица 1. Начальная часть файла частотныйСловарьЭлектроннаяВерсия.txt

http://dict.ruslang.ru/freq.php?act=show&dic=freq_freq&title=%D7%E0%F1%F2%EE%F2%ED%FB%E9%20%F1%EF%E8%F1%EE%EA%20%EB%E5%EC%EC
О. Н. Ляшевская, С. А. Шаров
НОВЫЙ ЧАСТОТНЫЙ СЛОВАРЬ РУССКОЙ ЛЕКСИКИ
Электронная версия издания:
О. Н. Ляшевская, С. А. Шаров, Частотный словарь современного русского языка (на материалах Национального корпуса русского языка). М.: Азбуковник, 2009.
Частотный список лемм
ЛеммаЛеммаЧасть речиЧастота (ipm)Худ.лит.1950-60-е1970-80-е1990-2000-еПубл. 1950-60-е1970-80-е1990-2000-е
1   ииconj35801.837546.039187.736514.736703.638352.135539.5
2   ввpr31374.223943.525005.726185.735295.333264.336372.5
3   ненеpart18028.021154.322921.522349.116127.418796.916853.2

Таблица 2. Начальная часть файла freqListWiktionary.txt

https://en.wiktionary.org/wiki/Wiktionary:Frequency_lists/PG/2006/04/1-10000
Frequencies listed here are per billion. Fractions are limited to two decimal places. Case insensitive.
RankWordCount (per billion)
1the56271872
2of33950064
3and29944184

Начальные части файлов частотныйСловарь.txt и freqList.txt приведены в табл. 3 и табл. 4.

Таблица 3. Начальная часть файла частотныйСловарь.txt

и   35801.8
в   31374.2
не   18028.0

Таблица 4. Начальная часть файла freqList.txt

the  56271872
of  33950064
and  29944184

В первом столбце каждого файла приведено слово, а во втором – его частота.

Порядок правки слова

Предварительно по файлу частотныйСловарь.txt (или freqList.txt) процедурой Spelling формируется частотный словарь dictionary, каждый элемент которого – это пара "ключ и значение".
В качестве ключа выступает слово, а значения – его частота.
Пусть задано слово "карова". Чтобы получить "корова", реализуется следующая последовательность действий:

Реализация на C#

Программа реализована на 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

namespace WindowsFormsApplicationSpellCorrector
{
 public partial class FormSpellCorrector : Form
 {
  Spelling spelling;

  public FormSpellCorrector()
  {
   InitializeComponent();
   spelling = new Spelling(radioButtonRus.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);
   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)
  {
   spelling = new Spelling(radioButtonRus.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 = "";
  }
 }
 public class Spelling
 {
  private Dictionary<string, int> dictionary = new Dictionary<string, int>();
  private bool Rus;
  public bool writeListsChecked, twoLevelsChecked;
  // Формируем по файлу частотныйСловарь.txt или freqList.txt словарь слов с частотами их повторений
  // Первые три строки файла freqList.txt (разделитель - знак табуляции):
  // the 56271872
  // of 33950064
  // and 29944184
  public Spelling(bool RusChecked)
  {
   string fileContent, key;
   Rus = RusChecked;
   fileContent = File.ReadAllText((Rus ? "частотныйСловарь.txt" : "freqList.txt"));
   List<string> wordList = fileContent.Split(new string[] { "\n" }, StringSplitOptions.RemoveEmptyEntries).ToList();
   string[] arrS = new string[2];
   int freq; // Частота слова
   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
И вместо "граненый" будет дан ответ "ограниченный", поскольку его частота наибольшая среди кандидатов.
Область действия программы ограничивает частотный словарь, в котором не представлены некоторые части речи, например деепричастия.
Кроме того, если опираться на частотный словарь, то нужно учитывать, что для каждого вида текстов (художественных, технических, политических и пр.) нужно иметь "свои" словари.
Нелишне сказать, что более востребован поиск и исправление ошибок в предложении, для чего приведенная программа неприспособлена.

Источники

  1. How to Write a Spelling Corrector. http://norvig.com/spell-correct.html
  2. How to Write a Spelling Corrector in C#. http://www.anotherchris.net/csharp/how-to-write-a-spelling-corrector-in-csharp/
  3. О. Н. Ляшевская, С. А. Шаров, Частотный словарь современного русского языка (на материалах Национального корпуса русского языка). М.: Азбуковник, 2009. Электронная версия. http://dict.ruslang.ru/freq.php?act=show&dic=freq_freq&title=%D7%E0%F1%F2%EE%F2%ED%FB%E9%20%F1%EF%E8%F1%EE%EA%20%EB%E5%EC%EC
  4. Wiktionary:Frequency lists/PG/2006/04/1-10000. https://en.wiktionary.org/wiki/Wiktionary:Frequency_lists/PG/2006/04/1-10000

Список работ

Рейтинг@Mail.ru