С Новым годом! Форум программистов, компьютерный форум, киберфорум
Java
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.71/35: Рейтинг темы: голосов - 35, средняя оценка - 4.71
31 / 31 / 6
Регистрация: 11.07.2013
Сообщений: 241

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

29.11.2013, 04:13. Показов 6751. Ответов 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
3176 / 1935 / 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
3176 / 1935 / 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
3176 / 1935 / 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
3176 / 1935 / 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
3176 / 1935 / 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
3176 / 1935 / 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
Ответ Создать тему
Новые блоги и статьи
Расчёт переходных процессов в цепи постоянного тока
igorrr37 16.01.2026
/ * Дана цепь постоянного тока с R, L, C, k(ключ), U, E, J. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа, решает её и находит токи на L и напряжения на C в установ. режимах до и. . .
Восстановить юзерскрипты Greasemonkey из бэкапа браузера
damix 15.01.2026
Если восстановить из бэкапа профиль Firefox после переустановки винды, то список юзерскриптов в Greasemonkey будет пустым. Но восстановить их можно так. Для этого понадобится консольная утилита. . .
Изучаю kubernetes
lagorue 13.01.2026
А пригодятся-ли мне знания kubernetes в России?
Сукцессия микоризы: основная теория в виде двух уравнений.
anaschu 11.01.2026
https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/
WordPad для Windows 11
Jel 10.01.2026
WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .
Classic Notepad for Windows 11
Jel 10.01.2026
Old Classic Notepad for Windows 11 Приложение для Windows 11, позволяющее пользователям вернуть классическую версию текстового редактора «Блокнот» из Windows 10. Программа предоставляет более. . .
Почему дизайн решает?
Neotwalker 09.01.2026
В современном мире, где конкуренция за внимание потребителя достигла пика, дизайн становится мощным инструментом для успеха бренда. Это не просто красивый внешний вид продукта или сайта — это. . .
Модель микоризы: классовый агентный подход 3
anaschu 06.01.2026
aa0a7f55b50dd51c5ec569d2d10c54f6/ O1rJuneU_ls https:/ / vkvideo. ru/ video-115721503_456239114
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru