31 / 31 / 6
Регистрация: 11.07.2013
Сообщений: 241

Поиск анаграмм в файле

29.11.2013, 04:13. Показов 6809. Ответов 12
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Здравствуйте! Такая задача:
Есть входной текстовой файл, в нем слова(какие попало и написаны как попало, а не красиво через пробел).
Нужно в другой текстовый файл записать все найденные анаграммы(из одних и тех же букв, одинаковая длина, каждая буква 1 раз, регистр не учитывается): одна строка - одна группа анаграмм

Пример:

Вход: Мама дай мне меН йад
Выход:

дай йад
мне меН


Учитывая, что размер входного файла может быть большим и даже очень большим, хорошая ли идея:

-Завести хешмапу <String, List<String>>, где String - слово, List<String> список всех анаграм для этого слова, включая его самого

-Прочитать файл до конца, заполнив эту мапу

-Переписывать из мапы в другой файл, если длина листа > 1

?


Может подскажете другую идею.
Спасибо
0
Лучшие ответы (1)
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
29.11.2013, 04:13
Ответы с готовыми решениями:

Поиск слова в файле
Задача найти все &quot;public&quot; и заменить на &quot;private&quot; и подсчитать сколько пабликов в файле. Найти , нашёл. А вот сколько их понять не могу...

Поиск ссылок в HTML файле
Здравствуйте! Возникла такая задача: на вход поступает url, идет по нему переход, в полученной странице(в виде HTML) ищутся все...

Поиск в файле
Поиск в файлах разных типов, разной структуры с разным результатом(разные файлы). Разного размера. Может кто посоветует в какую...

12
3178 / 1937 / 312
Регистрация: 27.08.2010
Сообщений: 5,131
Записей в блоге: 1
29.11.2013, 06:13
список всех анаграм для этого слова, включая его самого
Факториал от длины слова. И даже без учета повторов, все равно, слишком много.
Составьте, к примеру, список для "никотинамидадениндинуклеотидфосфатгидрин"

Задается словарь. Найти в нем все анаграммы
0
31 / 31 / 6
Регистрация: 11.07.2013
Сообщений: 241
29.11.2013, 06:56  [ТС]
Цитата Сообщение от gazlan Посмотреть сообщение
Факториал от длины слова.
Простите, не понял. Что будет факториал?

Добавлено через 1 минуту
Цитата Сообщение от gazlan Посмотреть сообщение
Составьте, к примеру, список для "никотинамидадениндинуклеотидфосфатгидри н"
Какой список? Список всех анаграм из групы, где есть слово никотинамидадениндинуклеотидфосфатгидрин ?

Добавлено через 3 минуты
Цитата Сообщение от gazlan Посмотреть сообщение
Составьте, к примеру, список для "никотинамидадениндинуклеотидфосфатгидри н"
дак в файле может вообще не быть анаграмм к этому слову
или я вас не понимаю
0
3178 / 1937 / 312
Регистрация: 27.08.2010
Сообщений: 5,131
Записей в блоге: 1
29.11.2013, 07:07
Цитата Сообщение от OxomHuK Посмотреть сообщение
или я вас не понимаю
Не понимаете. Смотрите алго по ссылке.
0
31 / 31 / 6
Регистрация: 11.07.2013
Сообщений: 241
29.11.2013, 07:27  [ТС]
вот я набросал код

Добавлено через 11 секунд
Java
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
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.PrintWriter;
import java.util.*;
 
 
public class FindAnagram {
 
    private boolean areAnagrams(String word1, String word2) {
        if (word1 == null || word2 == null || word1.length() != word2.length())
            return false;
        char[] ch1 = word1.toLowerCase().toCharArray();
        char[] ch2 = word2.toLowerCase().toCharArray();
        Arrays.sort(ch1);
        Arrays.sort(ch2);
        return Arrays.equals(ch1, ch2);
    }
 
    private boolean contains(Map<String, HashSet<String>> map, String word) {
        Set<String> keysSet = map.keySet();
        for (String key : keysSet) {
            if (areAnagrams(key, word))
                return true;
        }
        return false;
    }
 
    private String keyForAnagram(Map<String, HashSet<String>> map, String anagram) {
        Set<String> keysSet = map.keySet();
        for (String key : keysSet) {
            if (areAnagrams(key, anagram))
                return key;
        }
        return null;
    }
 
    public void findAnagrams(File from, File to) throws FileNotFoundException {
        Map<String, HashSet<String>> map = new HashMap<String, HashSet<String>>();
        Scanner sc = new Scanner(from, "Cp1251");
        PrintWriter out = new PrintWriter(new FileOutputStream(to));
 
        //чтение из файла в map
        while (sc.hasNextLine()) {
            String line = sc.nextLine();
           // String[] words = line.split("\\s+");
            String[] words = line.split("[,;:.!?\\s]+");
 
            for (String word : words) {
                if (!contains(map, word)) {
                    map.put(word, new HashSet<String>());
                    HashSet<String> set = map.get(word);
                    set.add(word);
 
                } else {
                    String key = keyForAnagram(map, word);
                    HashSet<String> set = map.get(key);
                    set.add(word);
                }
            }
        }      
 
        //запись из map в другой файл
        Set<String> keys = map.keySet();
        for (String key : keys) {
            if (map.get(key).size() > 1) {
                Set<String> anagrams = map.get(key);
                for (String anagram : anagrams) {
                    out.print(anagram + " ");
                }
                out.println();
            }
        }
        sc.close();
        out.close();
    }
 
    public static void main(String[] args) {
        try {
        File from = new File("C:\\file_from.txt");
        File to = new File("C:\\file_to.txt");
        new FindAnagram().findAnagrams(from, to);
        } catch(FileNotFoundException e) {
            System.out.println("File not found " + e.getMessage());
        }
    }
}
Добавлено через 1 минуту
вы мне обьясните, пожалуйста, почему так как у меня плохо(в каком конкретно месте)

Добавлено через 1 минуту
еще вопрос: из файла все слова нужно же куда то сохранять в память, правильно? Не map дак list
0
3178 / 1937 / 312
Регистрация: 27.08.2010
Сообщений: 5,131
Записей в блоге: 1
29.11.2013, 07:37
Цитата Сообщение от OxomHuK Посмотреть сообщение
Код Java(TM)
На Джаве не пишу и читать не люблю. Так что, могу понять неверно. Дождитесь комментариев тех, кто знает этот язык лучше.
0
31 / 31 / 6
Регистрация: 11.07.2013
Сообщений: 241
29.11.2013, 08:00  [ТС]
скачал я ради интереса мастера и маргариту ~ 0.8M, запустил прогу, читала/записывала минут 10, это долго?
0
 Аватар для verylazy
462 / 462 / 71
Регистрация: 26.02.2013
Сообщений: 1,263
29.11.2013, 10:44
Лучший ответ Сообщение было отмечено как решение

Решение

Дошел вчера пешком до работы за 35 минут, это долго?
3
31 / 31 / 6
Регистрация: 11.07.2013
Сообщений: 241
29.11.2013, 22:45  [ТС]
Цитата Сообщение от verylazy Посмотреть сообщение
Дошел вчера пешком до работы за 35 минут, это долго?

Не по теме:

понял :D

0
3178 / 1937 / 312
Регистрация: 27.08.2010
Сообщений: 5,131
Записей в блоге: 1
30.11.2013, 02:14
минут 10, это долго?
Долго.

Интереса ради, написал на С с сохранением промежуточных результатов на диск. Скачал M&M, конвертировал в Win-1251 (~747 Kb), обрабатывается примерно 10 сек по наручным часам. Если не использовать диск, а держать все в памяти, скорость должна вырасти минимум на порядок.
Миниатюры
Поиск анаграмм в файле  
Вложения
Тип файла: 7z Булгаков.txt.7z (3.0 Кб, 7 просмотров)
Тип файла: 7z Anagrammer.7z (11.8 Кб, 23 просмотров)
1
31 / 31 / 6
Регистрация: 11.07.2013
Сообщений: 241
30.11.2013, 07:43  [ТС]
да, свою ошибку с алгоритмом я понял, переделываю на другой

Добавлено через 51 минуту
А подскажите пожалуйста, как из ArrayList<Parser> list1 получить ArrayList<ArrayList<String>>,

где
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import java.util.Arrays;
 
public class Parser {
    private String word;
    private String signature;
 
    public Parser(String word) {
        this.word = word;
        char[] wordToCharArray = word.toLowerCase().toCharArray();
        Arrays.sort(wordToCharArray);
        signature = new String(wordToCharArray);
    }
 
    public String getWord() {
        return word;
    }
 
    public String getSignature() {
        return signature;
    }
}
То есть, есть список обьектов, каждый из которых хранит слово и строку, которая = это же слово, отсортированное по буквам
Этот список list 1 отсортирован вот по этим строкам

Например:
list1 = {(pans, aups), (snap, aups), (pots, opst), (stop, opst), (tops, opst), (opt, opt)}

Как мне из него получить список списков строк(списков анаграм), то есть:

list2 = {<pans, snap>, <pots, stop, tops>}
// если для слова не нашлась анаграмма в list1 то его не нужно заносить в список list2

Спасибо

Добавлено через 59 минут
разобрался, переписал алгоритм, теперь для 1М работает за 1 секундку....

Не по теме:

а было 10 минут:-[



Добавлено через 3 часа 12 минут
задам еще вопрос:
когда я читаю из файла(предположим 10М ~1_000_000 слов) в память и использую сканер
Java
1
2
3
4
5
6
7
8
9
10
 List<String> listOfWords = new ArrayList<String>();
 
        Scanner scanner = new Scanner(source, "UTF-8");
        while (scanner.hasNextLine()) {
            String line = scanner.nextLine();
            String[] words = line.split("[()…»«,;:.!?\\s]+");
            for (String word : words) {
                listOfWords.add(word);
            }
        }
то:
это(сканер а не допустим BufferedReader) нормально в принципе
это нормально только учитывая небольшой размер файла

ну то есть, при чтении очень большого файла(ну пускай аж до 1Г) сканером нормально пользоваться или есть альтернативы лучше?(подскажите)
0
3178 / 1937 / 312
Регистрация: 27.08.2010
Сообщений: 5,131
Записей в блоге: 1
30.11.2013, 10:15
при чтении очень большого файла
IMHO, неверно привязывать сканер к контейнеру - это разные сущности.

Сканер должен просматривать входной поток и выдавать очередную лексему (при необходимости, вместе с ее позицией в потоке и размером). Все. Внутреннее устройство файла (и есть ли там вообще "строки") не имеет значения - точно так же, на вход программы можно подать EXE-файл.

C++
1
2
3
4
5
6
7
   while (Length = GetWord())
   {
      if ((Length >= Min) && (Length <= Max))
      {
         // Insert Word into DB
      }
   }
Где хранить полученный список лексем - вопрос реализации, никак не связанный с разбором текста. У меня, например, это (собственная) On Disk Key-Value DB (B*Tree). С тем же успехом, это может быть любая реляционная DB - для (очень) больших файлов или In Memory DB для игрушечных задач.

Впрочем, для естественного языка можно ожидать словарь порядка 100,000 уникальных слов даже для произвольно больших файлов и, если при вставке в DB сразу проверять дубликаты, то, ценой некоторого замедления, вполне можно хранить все в RAM (считая среднюю длину слова 10 байт (не Unicode), это всего 1 Mb нетто).
Миниатюры
Поиск анаграмм в файле  
1
3178 / 1937 / 312
Регистрация: 27.08.2010
Сообщений: 5,131
Записей в блоге: 1
30.11.2013, 22:42
Музыкой навеяло.

Словарь русских анаграмм. Составлен по большому (3,032,693) словарю лексем. В файле lexicon.469979.txt содержится отсортированный по алфавиту список всех уникальных слов. Может быть использован для быстрого просмотра/поиска. Если слово есть в лексиконе, то к нему существует анаграмма.

Ex: ЯЩЕРИЦА -- ЦАРЯЩИЕ
Вложения
Тип файла: 7z anagrams.russian.7z (1.97 Мб, 38 просмотров)
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
30.11.2013, 22:42
Помогаю со студенческими работами здесь

Поиск в файле
Найти в файле числа

Поиск слова в файле
Доброго времени суток. Мне нужно из текстового файла найти заданное слово и вывести его в консоль. Я написал примерный код, но слово...

Поиск слова в файле
Написать программу для поиска слова в файле, программа должна показать: количество таких слов в файле, для каждого найденного слова: номер...

Поиск чисел в текстовом файле
Нужно найти самое большое число в каждой строчке текстового файла и вывести их.

Поиск слова в текстовом файле
Разработать программу, которая читает текстовый файл и некоторое слово и выводит те строки файла, которые содержат данное слово. Имя...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
13
Ответ Создать тему
Опции темы

Новые блоги и статьи
Модель заражения группы наркоманов
alhaos 17.04.2026
Условия задачи сформулированы тут Суть: - Группа наркоманов из 10 человек. - Только один инфицирован ВИЧ. - Колются одной иглой. - Колются раз в день. - Колются последовательно через. . .
Мысли в слух. Про "навсегда".
kumehtar 16.04.2026
Подумалось тут, что наверное очень глупо использовать во всяких своих установках понятие "навсегда". Это очень сильное понятие, и я только начинаю понимать край его смысла, не смотря на то что давно. . .
My Business CRM
MaGz GoLd 16.04.2026
Всем привет, недавно возникла потребность создать CRM, для личных нужд. Собственно программа предоставляет из себя базу данных клиентов, в которой можно фиксировать звонки, стадии сделки, а также. . .
Знаешь почему 90% людей редко бывают счастливыми?
kumehtar 14.04.2026
Потому что они ждут. Ждут выходных, ждут отпуска, ждут удачного момента. . . а удачный момент так и не приходит.
Фиксация колонок в отчете СКД
Maks 14.04.2026
Фиксация колонок в СКД отчета типа Таблица. Задача: зафиксировать три левых колонки в отчете. Процедура ПриКомпоновкеРезультата(ДокументРезультат, ДанныеРасшифровки, СтандартнаяОбработка) / / . . .
Настройки VS Code
Loafer 13.04.2026
{ "cmake. configureOnOpen": false, "diffEditor. ignoreTrimWhitespace": true, "editor. guides. bracketPairs": "active", "extensions. ignoreRecommendations": true, . . .
Оптимизация кода на разграничение прав доступа к элементам формы
Maks 13.04.2026
Алгоритм из решения ниже реализован на нетиповом документе, разработанного в конфигурации КА2. Задачи, как таковой, поставлено не было, проделанное ниже исключительно моя инициатива. Было так:. . .
Контроль заполнения и очистка дат в зависимости от значения перечислений
Maks 12.04.2026
Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: реализовать контроль корректности заполнения дат назначения. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru