Поиск анаграмм географических названий (в ГБ)

Некоторое время назад Аласдэр Рей спросил, объединил ли кто-нибудь механизм анаграмм со списком географических названий.

Ну, никто не выступил вперед, так что я подумал, что это будет забавный проект. И, оказывается, это довольно забавно, хотя мне приходится больше думать о структурах данных, чем о географии, но это, вероятно, хорошо для меня.

Я предположил, что Аласдера, вероятно, интересовали не просто перестановки букв, а настоящие слова (такие, которые использовались бы в разгадке кроссворда). Я также ограничил свой поиск анаграммами из одного слова, поскольку не вижу простого решения для поиска решений из нескольких слов.

Сначала я загрузил набор данных открытых имен Ordnance Survey в PostGIS (как кто хочет сканировать сотни маленьких csv-файлов).

Затем я настроил Геоинструменты PostGIS хранилище данных и захватил населенные пункты.

Map params = new HashMap();
    params.put(PostgisNGDataStoreFactory.DBTYPE.key, PostgisNGDataStoreFactory.DBTYPE.sample);
    params.put(PostgisNGDataStoreFactory.USER.key, "username");
    params.put(PostgisNGDataStoreFactory.PASSWD.key, "password");
    params.put(PostgisNGDataStoreFactory.SCHEMA.key, "opennames");
    params.put(PostgisNGDataStoreFactory.DATABASE.key, "osdata");
    params.put(PostgisNGDataStoreFactory.HOST.key, "127.0.0.1");
    params.put(PostgisNGDataStoreFactory.PORT.key, "5432");

      DataStore ds = DataStoreFinder.getDataStore(params);
    if (ds == null) {
      throw new RuntimeException("No datastore");
    }
    SimpleFeatureSource fs = ds.getFeatureSource("opennames");
    SimpleFeatureCollection features = fs.getFeatures(CQL.toFilter("type = 'populatedPlace'"));

Я попробовал наивный подход, заключающийся в рекурсивном поиске каждой возможной анаграммы из имени и поиске каждой из них в HashMap английских слов. Как ни странно, это заняло много времени, поэтому я подумал (и погуглил) еще немного и придумал гораздо более эффективный способ сортировки букв в слове и использования его в качестве ключа ко всем словам, содержащим эти буквы. Затем я мог бы отсортировать буквы каждого названия места и выполнить единый поиск, чтобы найти все возможные слова, которые можно было бы составить из этих букв. Это здорово ускорило процесс.

Чтобы создать таблицу поиска, я использовал Google HashMultimap (из Guava ) , который позволяет вам создавать Карту из Коллекций с ключом на Строке .

private Map> dict;

  public AnagramLookup() throws FileNotFoundException, IOException {
    //change this to point to your dictionary (one word per line)
    File f = new File("/usr/share/dict/british-english");
    HashMultimap indexedDictionary = HashMultimap.create();
    try (BufferedReader buf = new BufferedReader(new FileReader(f))) {
      String line;
      // read each word in the dictionary
      while ((line = buf.readLine()) != null) {
        //strip out non letters
        String word = line.toLowerCase().replaceAll("\\W", "");
        //store the word against the sorted key
        indexedDictionary.put(sort(word), word);
      }
    }
    dict = indexedDictionary.asMap();
  }

Затем все, что осталось сделать, это перебрать каждое населенное место, захватить его имя, а затем удалить все не-буквы, отсортировать его по буквам и просмотреть анаграммы в HashMap . Последний трюк состоит в том, чтобы удалить само имя, если оно появляется в списке анаграмм (т.Е. Само имя является английским словом).

try (SimpleFeatureIterator itr = features.features()) {

      while (itr.hasNext()) {

        SimpleFeature f = itr.next();
        String name = (String) f.getAttribute("name1");

        current = name.toLowerCase().replaceAll("\\W", "");
        Collection anagrams = getAnagrams(current);

        if(anagrams!=null && !anagrams.isEmpty()) {
          //remove the name itself if it happens to be a word
          anagrams.remove(current);
          if(!anagrams.isEmpty()) {
            results.put(name, new TreeSet(anagrams));
          }
        }
      }
    }

Результаты

Оказывается, существует 6 11-буквенных анаграмм для списка географических названий ГБ.

• Бальнадельсон – белладонна
• Fortis Green – освежающий
• Гиллинг Ист – законотворчество
• Зеленые равнины – шпенглеровский
• Морнингсайд – модернизация
• Харрингтон – харрингтоны
• Каменный угол – краеугольный камень

A Шпенглеровская – это “теория всемирной истории, разработанная Освальдом Шпенглером или относящаяся к ней, которая утверждает, что все основные культуры проходят одинаковый циклический путь развития от рождения до зрелости и упадка”. В то время как Harrington – это “мужская короткая легкая куртка с воротником и застежкой на молнию спереди”.

Другие достопримечательности для любителей разгадывать кроссворды включают Эймс-Грин в качестве зверинца и Уэст-Линтон в качестве тинселтауна.

Я опубликовал полный список анаграмм и код для создания списка .

Смотрите это продолжение для получения мировых названий.

Оригинал: “https://dev.to/ianturton/finding-anagrams-of-place-names-in-gb-3o38”