Поиск значения с помощью ключа или наоборот

Question

Прежде всего, извинения за неприятный заголовок.Я исправлю это позже.

У меня есть некоторые данные, как показано ниже,

"BOULEVARD","BOUL","BOULV", "BLVD"

Мне нужна структура данных O (1) для поиска любого изэто слова другими.Например, если я использую словарь, мне нужно будет хранить эти ключи / значения, как это, что выглядит странно для меня,

abbr.Add("BLVD", new List<string> { "BOULEVARD","BOUL","BOULV", "BLVD" });
abbr.Add("BOUL", new List<string> { "BOULEVARD", "BOUL", "BOULV", "BLVD" });
abbr.Add("BOULV", new List<string> { "BOULEVARD", "BOUL", "BOULV", "BLVD" });
abbr.Add("BOULEVARD", new List<string> { "BOULEVARD", "BOUL", "BOULV", "BLVD" });

Какую структуру данных использовать, чтобы эти данные соответствовали моим условиям запроса?

Заранее спасибо

Answer 1

Если вы не создадите новый список для каждого ключа, то Dictionary<string, List<string>> будет быстрым и разумно эффективным, если объем данных невелик.Вы также можете получить дополнительную выгоду от повторного использования самих строк, хотя оптимизатор может позаботиться об этом за вас.

var abbr = new Dictionary<string, List<string>>;

var values = new List<string> { "BOULEVARD","BOUL","BOULV", "BLVD" };

foreach(var aValue in values) abbr.add(value, values);

Answer 2

Выбор словаря мне подходит.Как упоминалось выше, вы должны использовать тот же список, на который ссылаются в словаре.Код может выглядеть примерно так:

var allAbrList = new List<List<string>>
                 {
                    new List<string> {"BOULEVARD", "BOUL", "BOULV", "BLVD"},
                    new List<string> {"STREET", "ST", "STR"},
                    // ...
                 };

var allAbrLookup = new Dictionary<string, List<string>>();
foreach (List<string> list in allAbrList)
{
    foreach (string abbr in list)
    {
        allAbrLookup.Add(abbr, list);
    }
}

Последняя часть может быть преобразована в LINQ, чтобы иметь меньше кода, но таким образом это легче понять.

Answer 3

Предполагая, что abbr является Dictionary<String, IEnumerable<String>>, вы можете использовать следующую функцию:

public static void IndexAbbreviations(IEnumerable<String> abbreviations) {
    for (var a in abbreviations)
        abbr.Add(a, abbreviations);
}

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

Из документации «Получение значения с использованием его ключа выполняется очень быстро, близко к O (1), поскольку класс Dictionary (Of TKey, TValue) реализован как хешстол. "

Answer 4

Создать два HashMap - одно сопоставление слова с номером группы.А другой отображает номер группы в список слов.Таким образом, вы экономите память.

Map<String, Integer> - Word to Group Number
Map<Integer, List<String>> - Group Number to a list of words

Вам нужно два O(1) поиска - сначала для получения номера группы, а затем по нему - для получения списка слов.

Answer 5

Как уже сказал Петр Минчев, вы можете разбить свой список на список групп и список ключей, которые указывают на эту группу. Чтобы упростить это (при использовании), вы можете написать собственную реализацию IDictionary и использовать метод Add для построения этих групп. Я дал ему попробовать, и это похоже на работу. Вот важные части реализации:

public class GroupedDictionary<T> : IDictionary<T,IList<T>>
{
    private Dictionary<T, int> _keys;
    private Dictionary<int, IList<T>> _valueGroups;

    public GroupedDictionary()
    {
        _keys = new Dictionary<T, int>();
        _valueGroups = new Dictionary<int, IList<T>>();
    }

    public void Add(KeyValuePair<T, IList<T>> item)
    {
        Add(item.Key, item.Value);
    }

    public void Add(T key, IList<T> value)
    {
        // look if some of the values already exist
        int existingGroupKey = -1;
        foreach (T v in value)
        {
            if (_keys.Keys.Contains(v))
            {
                existingGroupKey = _keys[v];
                break;
            }
        }
        if (existingGroupKey == -1)
        {
            // new group
            int newGroupKey = _valueGroups.Count;
            _valueGroups.Add(newGroupKey, new List<T>(value));
            _valueGroups[newGroupKey].Add(key);
            foreach (T v in value)
            {
                _keys.Add(v, newGroupKey);
            }
            _keys.Add(key, newGroupKey);
        }
        else
        {
            // existing group
            _valueGroups[existingGroupKey].Add(key);
            // add items that are new
            foreach (T v in value)
            {
                if(!_valueGroups[existingGroupKey].Contains(v))
                {
                    _valueGroups[existingGroupKey].Add(v);
                }
            }
            // add new keys
            _keys.Add(key, existingGroupKey);
            foreach (T v in value)
            {
                if (!_keys.Keys.Contains(v))
                {
                    _keys.Add(v, existingGroupKey);
                }
            }
        }
    }

    public IList<T> this[T key]
    {
        get { return _valueGroups[_keys[key]]; }
        set { throw new NotImplementedException(); }
    }
}

Использование может выглядеть так:

var groupedDictionary = new GroupedDictionary<string>();
groupedDictionary.Add("BLVD", new List<string> {"BOUL", "BOULV"}); // after that three keys exist and one list of three items
groupedDictionary.Add("BOULEVARD", new List<string> {"BLVD"}); // now there is a fourth key and the key is added to the existing list instance
var items = groupedDictionary["BOULV"]; // will give you the list with four items

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

Answer 6

Не вижу смысла определять часть значения вашего словаря как объект List<string>, но, возможно, это ваше требование. Этот ответ предполагает, что вы просто хотите узнать, означает ли это слово «бульвар».

Я бы выбрал одно значение в качестве «официального» значения и сопоставил бы все остальные значения, например:

        var abbr = new Dictionary<string, string>(StringComparer.CurrentCultureIgnoreCase);

        abbr.Add("BLVD", "BLVD"); // this line may be optional
        abbr.Add("BOUL", "BLVD");
        abbr.Add("BOULV", "BLVD");
        abbr.Add("BOULEVARD", "BLVD");

В качестве альтернативы, вы можете определить перечисление для части значения словаря, как показано ниже:

    enum AddressLine1Suffix
    {
        Road,
        Street,
        Avenue,
        Boulevard,
    }


        var abbr = new Dictionary<string, AddressLine1Suffix>(StringComparer.CurrentCultureIgnoreCase);

        abbr.Add("BLVD", AddressLine1Suffix.Boulevard);
        abbr.Add("BOUL", AddressLine1Suffix.Boulevard);
        abbr.Add("BOULV", AddressLine1Suffix.Boulevard);
        abbr.Add("BOULEVARD", AddressLine1Suffix.Boulevard);