حالة القاسي ترناري البحث شجرة

Question

وكنت قد تم استخدام ترناري البحث شجرة لفترة من الوقت، وبنية البيانات لتنفيذ انخفاض استكمال السيارات مربع التحرير والسرد إلى أسفل. وهو ما يعني، عندما نوع المستخدم "FO"، وانخفاض مربع التحرير والسرد أسفل عرض

وفو طعام كرة القدم

والمشكلة هي، يا المستخدمة من ترناري البحث شجرة الحالية هي حالة الأحرف. تنفيذ بلدي هي على النحو التالي. تم استخدامه من قبل العالم الحقيقي لحوالي 1 ++ الاعوام. ومن هنا، أرى أنها موثوق بها تماما.

<وأ href = "http://jstock.cvs.sourceforge.net/viewvc/jstock/jstock/src/org/yccheok/jstock/engine/TernarySearchTree.java؟view=markup" يختلط = "نوفولو noreferrer" > بلدي ترناري البحث شجرة كود

ولكن، أنا أبحث عن قضية حساسة ترناري البحث شجرة، وهو ما يعني، عندما كنت اكتب "FO"، وانخفاض مربع التحرير والسرد أسفل سوف تظهر لي

وفو طعام كرة القدم

وهنا بعض اجهة رئيسية لتجارة الرقيق عبر الأطلسي، حيث آمل أن حالة جديدة insentive تجارة الرقيق عبر الأطلسي قد يكون واجهة مشابهة جدا.

    /** 
 * Stores value in the TernarySearchTree. The value may be retrieved using key.
 * @param key A string that indexes the object to be stored.
 * @param value The object to be stored in the tree.
 */    
public void put(String key, E value) {
    getOrCreateNode(key).data = value;
}

/**
 * Retrieve the object indexed by key.
 * @param key A String index.
 * @return Object The object retrieved from the TernarySearchTree.
 */
public E get(String key) {
    TSTNode<E> node = getNode(key);
    if(node==null) return null;
    return node.data;
}

ومثال على الاستخدام هي على النحو التالي. TSTSearchEngine تستخدم TernarySearchTree باعتبارها العمود الفقري الأساسية.

<وأ href = "http://jstock.cvs.sourceforge.net/viewvc/jstock/jstock/src/org/yccheok/jstock/engine/TSTSearchEngine.java؟revision=1.2&view=markup" يختلط = " نوفولو noreferrer "> الاستخدام مثال على ترناري البحث شجرة

// There is stock named microsoft and MICROChip inside stocks ArrayList.
TSTSearchEngine<Stock> engine = TSTSearchEngine<Stock>(stocks);
// I wish it would return microsoft and MICROCHIP. Currently, it just return microsoft.
List<Stock> results = engine.searchAll("micro"); 

Answer 1

واحدة من العوامل الرئيسية التي تجعل بلدي الحالية ترناري البحث شجرة الصعب لدعم قضية حساسة البحث هو أن يا بنية بيانات الأساسي هو رسم الخرائط واحد الى واحد. يرجى إلقاء نظرة على رمز اختبار التالية:

public void testPut() {
    System.out.println("put");
    Name name0 = new Name("abc");
    Name name1 = new Name("abc");
    TernarySearchTree<Name> instance = new TernarySearchTree<Name>();
    instance.put(name0.toString(), name0);
    instance.put(name1.toString(), name1);
    assertEquals(2, instance.matchPrefix("a").size()); // fail here. Result is 1
}

وماذا حل بي الحالي على المدى القصير هو أن أستخدمه TSTSearchEngine لانهاء TernarySearchTree كله. وتتألف TSTSearchEngine من

و(1) TernarySearchTree، وتوفير مفتاح UPPER-CASE إلى الخريطة.

(2) سلسلة إلى ArrayList خريطة.

وهنا هو ما يحدث عندما أقوم:

TSTSearchEngine<Name> engine = TSTSearchEngine<Name>();
engine.put(name0); // name0 is new Name("Abc");
engine.put(name1); // name0 is new Name("aBc");

و(1) name0.toString () سيتم تحويلها إلى UPPER-CASE ( "ABC"). سيتم إدخاله إلى TernarySearchTree. "ABC" ستكون على حد سواء المفاتيح والقيم للTernarySearchTree.

(2) "ABC" سوف تستخدم كمفتاح للخريطة، لإدراج NAME0 في قائمة مجموعة.

(3) name1.toString سيتم تحويل () إلى UPPER-CASE ( "ABC"). سيتم إدخاله إلى TernarySearchTree. سوف S1 تكون كلا المفاتيح والقيم للTernarySearchTree.

(4) "ABC" سوف تستخدم كمفتاح للخريطة، لإدراج NAME1 إلى قائمة مجموعة.

وعندما أحاول

engine.searchAll("a");

و(1) سوف TernarySearchTree العودة "ABC".

(2) "ABC" سيتم استخدامها كمفتاح للوصول إلى خريطة. سوف خريطة بإرجاع قائمة مجموعة التي تحتوي على NAME0 وNAME1.

ويعمل هذا الحل. نموذج التعليمات البرمجية يمكن الإشارة إلى <لأ href = "http://jstock.cvs.sourceforge.net/viewvc/jstock/jstock/src/org/yccheok/jstock/engine/TSTSearchEngine.java؟view=markup" يختلط = "نوفولو noreferrer"> نموذج التعليمات البرمجية ل New TSTSearchEngine

ولكن هذا قد لا يكون حلا فعالا، لأنه يتطلب اثنين من تمريرة من البحث. أجد من وجود التنفيذ في C ++ C ++ تنفيذ حالة غير حساس ترناري البحث شجرة . وبالتالي، هناك فرصة هذا الرمز C ++ يمكن استدار لأكثر من جافا.

Answer 2

وأنا لم تستخدم في تجارة الرقيق عبر الأطلسي من قبل، ولكن ليس هذا بسيطا قدر أقل أو uppercasing المفاتيح الخاصة بك، سواء أثناء التخزين وأثناء البحث؟ من التعليمات البرمجية مقتطف يبدو أن يجب أن تعمل.

Answer 3

ولقد نفذت شجرة البحث الثلاثي، يمكنك إلقاء نظرة على الموقع http://kunalekawde.blogspot.com/2010/05/radix-patricia-and-ternary.html اعتبارا من حالة insensative، إما أن الخريطة الصغيرة والقبعات لعرافة قيمة واحدة / ديسمبر أو حين الحصول على البادئة، والتحقق من القيمة.