Like Kjeld mention it in another thread, there has been a lot of migrations from the Asian mainland to the islands of Indonesia and Japan during the ice age. I recommend a very good book on the development and migration of human societies : Guns, Germs, and Steel, by Jared Diamond.
Indonesians, Malaysians and Philipinos actually originate from Southern China. They'd have migrated on boats via Taiwan and displace the original inhabitants that might have been related to Dravidians of Southern India. In Papua-New Guinea, the indigenous people were more numerous and well settled, so that they had to go around them and continued to Polynesia (all the pacific islands) and New Zealand. With pimitive boats, they were able to travel as far as Hawai or the Easter Islands. Linguistically, all polynesian languages, from Hawai to the Fiji and New Zealand, via the Marianias, Kiribati, Tuvalu, etc. are closely related. They are related to Indonesians languages as well. Differences between regions increase with the time they were settled, not the distance between them. So, 2 groups of islands in the pacific might be 500km away, but the inhabitants of one may only have been settled a few generations away by inhabitants of the other group.
Indonesians ?
I have noticed myself quite a few similarities between Bahasa Indonesia/Malaysia and Japanese language. Apart from the very similar pronounciation in both languages, there is the same hierarchical differences in personal pronouns. For example "you" is either "anda" or "kamu" with the same meaning and wa of using as "anata" and "kimi" in Japanese. Likewise, "suki" D (to like) translates "suka" in Bahasa. Such similarities are striking. In both languages you can make a plural by doubling the word, like wareware in Japanese (ware = I or you, wareware = we). Doubling of words is so common that there is a kanji that only means the word is doubled(" X") in written Japanese. However, it is more common in Bahasa nowadays where it is almost systematical. Expressions like "ittekimasu, itteirashai, tadaima and okaeri" also exist in Indonesian (selamat jalan, selamat tinggal...), but not in European languages. I am not a specialist of any of these languages at all. I barely know a few words in Indonesian, but it's enough to see the link with Japanese.
Japanese matsuri ressembles so much Balinese ones that one could wonder if they are actually the same country. I've seen a cremation in Bali ; they cary the dead body very much like Japanese carry a mikoshi. Balinese funerals are joyful and people swinging the "mikoshi" in the streets and making loud noise to scare the evil sprits. Basically, Bali is Hindu, but has mixed it with the original animist religion. Shinto is also an animisn, and we can see lots of other cultural similarities between non-muslim/non-christian Indonesia and non-buddhist Japan. For example, the wall and entrance around traditional houses and the style of Balinese temples and Japanese shrines. Buddhism, Islam and Christianity all arrived much later after the supposed original ancestors of the 2 archipelago split from each other, but have changed radically both societies. We have to look for the purely original culture (what might be very difficult nowadays) to find the connection existing in late prehistoric time.
Koreans ?
Japanese and Korean grammar are very similar. My Koreans acquaintances in Japan told me that some words were also almost identical, such as kazoku, sentaku or hakkiri. Both languages are classsified in the Altaic group of languages. Check this comparison of Altaic languages together.
About half of Japanese vocabulary comes from Chinese via kanji compounds. However, it seems that there hasn't been any much direct migration from China to Japan, except a few scholars or monks. But ultimately, going back a few millenia, all East Asian are from Chinese-Mongolian origin. Linguistically and culturally, Japanese are closer to Koreans and Indonesians.
Bookmarks