Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > Java: Общие вопросы > Сортировка текста в алфавитном порядке в TreeSet


Автор: Kizja 9.3.2010, 00:39
Привет!

Хотел сделать сортировщик текста в алфавитном порядке, используя TreeSet, однако обнаружил, что сортируются правильно не все языки...

В приведённом тесте пытаюсь сортировать алфавиты английского, немецкого, русского и эстонского языков. Первые два работают правильно... Однако тесты русского и эстонского языка не проходят:

1) В русском ставит букву "Ё" вперёд всех остальных
2) В эстонском ставит в неверные места буквы "Š", "Ž", "Õ", "Ä"

Код

import static org.junit.Assert.assertArrayEquals;

import java.util.Arrays;
import java.util.Set;
import java.util.TreeSet;

import org.junit.Ignore;
import org.junit.Test;


public class AlphabetTest {
    private static final String ENG = 
        "A B C D E F G H I J K L M N O P Q R S T U V W X Y Z";
    private static final String GER = 
        "A B C D E F G H I J K L M N O P Q R S T U V W X Y Z Ä Ö Ü ß";
    private static final String RUS = 
        "А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я";
    private static final String EST = 
        "A B D E F G H I J K L M N O P R S Š Z Ž T U V Õ Ä Ö Ü";
    
    @Test
    public void eng() throws Exception {
        assertArrayEquals(split(ENG), sort(ENG));
    }
    
    @Test
    public void ger() throws Exception {
        assertArrayEquals(split(GER), sort(GER));
    }
    
    @Test
    public void rus() throws Exception {
        assertArrayEquals(split(RUS), sort(RUS));
    }
    
    @Test
    public void est() throws Exception {
        assertArrayEquals(split(EST), sort(EST));
    }
    
    private String[] sort(String alphabet) {
        Set<String> set = new TreeSet<String>(Arrays.asList(split(alphabet)));
        return set.toArray(new String[set.size()]);
    }
    
    private String[] split(String string) {
        return string.split(" ");
    }
}


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

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

Я не думаю, что первый кто столкнулся с проблемой сортировки по алфавиту... Почти в любом веб приложении существует сортировка колонок в алфавитном порядке...

Поэтому собственно вопрос - как изменить данный код, чтобы он работал бы верно и для русского и эстонского языков ? Т.е. можно ли сделать какой-то универсальный сортировщик, который бы работал верно для любого языка ?

Автор: LSD 9.3.2010, 13:59
А чем не устраивает http://java.sun.com/j2se/1.5.0/docs/api/java/text/Collator.html?

Автор: Kizja 13.3.2010, 03:23
LSD, спасибо, не знал про Collator и вобщем-то данный тест с ним работает, но я здесь привёл несколько упрощённый вариант того, чего мне хотелось бы добиться... 

А именно хотел получить сортировку слов в алфавитном порядке и в этом случае Collator ведёт себя в некоторых случаях не очень адекватно. 

Например пробовал тестировать эстонский текст и в словах текста были буквы "V" и "W" - оказалось, что он их не различает и в результате сортировки получаются слова с этими буквами вперемешку, т.е. например выдаёт Va, Wb, Vc, Wd вместо Va, Vc, Wb, Wd - т.е. сортирует по последующим буквам, а "V" и "W" расценивает как одну и ту же букву.

Автор: Vier 15.3.2010, 13:58
Можно сделать один comparator и передавать ему алфавитную строку.

Автор: LSD 17.3.2010, 19:35
Хотелось бы маленький пример с демонстрацией ошибки.

Автор: Kizja 18.3.2010, 22:34
LSD, добавил в тот пример, который приводил выше, сортировку с Collator-ом...

Код

import static org.junit.Assert.assertArrayEquals;

import java.text.Collator;
import java.util.Arrays;
import java.util.Locale;
import java.util.Set;
import java.util.TreeSet;

import org.junit.Test;

public class AlphabetTest {
    private static final String ENG = 
        "A B C D E F G H I J K L M N O P Q R S T U Va Vc Wb Wd X Y Z";
    private static final String GER = 
        "A B C D E F G H I J K L M N O P Q R S T U Va Vc Wb Wd X Y Z Ä Ö Ü ß";
    private static final String RUS = 
        "А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я";
    private static final String EST = 
        "A B D E F G H I J K L M N O P R S Š Z Ž T U Va Vc Wb Wd Õ Ä Ö Ü";
    
    @Test
    public void eng() throws Exception {
        print(collatorSort(ENG, Locale.ENGLISH));
        assertArrayEquals(split(ENG), collatorSort(ENG, Locale.ENGLISH));
        assertArrayEquals(split(ENG), sort(ENG));
    }
    
    @Test
    public void ger() throws Exception {
        print(collatorSort(ENG, Locale.GERMAN));
        assertArrayEquals(split(ENG), collatorSort(ENG, Locale.GERMAN));
        assertArrayEquals(split(GER), sort(GER));
    }
    
    @Test
    public void rus() throws Exception {
        print(sort(RUS));
        assertArrayEquals(split(RUS), sort(RUS));
    }
    
    @Test
    public void rusCollator() throws Exception {
        print(collatorSort(RUS, new Locale("ru")));
        assertArrayEquals(split(RUS), collatorSort(RUS, new Locale("ru")));
    }
    
    @Test
    public void est() throws Exception {
        print(sort(EST));
        assertArrayEquals(split(EST), sort(EST));
    }
    
    @Test
    public void estCollator() throws Exception {
        print(collatorSort(EST, new Locale("et")));
        assertArrayEquals(split(EST), collatorSort(EST, new Locale("et")));
    }
    
    private void print(String[] strings) {
        for (String string : strings) {
            System.out.print(string + " ");
        }
        System.out.println();
    }
    
    private String[] collatorSort(String alphabet, Locale locale) {
        return sort(new TreeSet<String>(
                Collator.getInstance(locale)), alphabet);
    }
    
    private String[] sort(String alphabet) {
        return sort(new TreeSet<String>(), alphabet);
    }
    
    private String[] sort(Set<String> set, String alphabet) {
        set.addAll(Arrays.asList(split(alphabet)));
        return set.toArray(new String[set.size()]);
    }
    
    private String[] split(String string) {
        return string.split(" ");
    }
}


Для русского языка не проходит тест без Collator-а: ставит "Ё" вперёд остальных букв. Возможно кстати и с Collator-ом в каком-то случае тоже не пройдёт, но я не обнаружил пока что.

Для эстонского языка не проходят оба теста: без Collator-а сортирует неправильно буквы "Š", "Ž", "Õ", "Ä", а для варианта с Collator-ом ставит неверно Va, Wb, Vc, Wd

Вот выводимый результат:

Код

A B C D E F G H I J K L M N O P Q R S T U Va Vc Wb Wd X Y Z 
A B C D E F G H I J K L M N O P Q R S T U Va Vc Wb Wd X Y Z 
Ё А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я 
А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я 
A B D E F G H I J K L M N O P R S Š Z Ž T U Va Wb Vc Wd Õ Ä Ö Ü 
A B D E F G H I J K L M N O P R S T U Va Vc Wb Wd Z Ä Õ Ö Ü Š Ž 


Автор: LSD 25.3.2010, 17:14
Ну не факт, что это неправильно:
Цитата
Some letters only occur in foreign words and foreign proper names that can also contain other Latin-based letters

http://www.einst.ee/publications/language/alphabet.html

Цитата
Personal names, placenames and quotations of foreign origin also need additional letters of the latin alphabet to be used, the most common ones are c, q, w, x, y, this is why they are bracketed.

http://www.eki.ee/keel/et003.html

Цитата
W — Фактически не используется в современном эстонском

http://ru.wikipedia.org/wiki/%D0%AD%D1%81%D1%82%D0%BE%D0%BD%D1%81%D0%BA%D0%B8%D0%B9_%D0%B0%D0%BB%D1%84%D0%B0%D0%B2%D0%B8%D1%82
Т.е. W как-то по особому может обрабатываться в эстонском. Так что возможно, что так и надо сортировать. В любом случае, это уже лучше с лингвистами разговаривать.

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)